比较简单的 DP 题目。
数的值域很小,考虑将其压入状态。设计 $f(i,j)$ 表示第 $i$ 为 $j$ 的合法方案数。$sum(i)=\sum_{j=0}^k f(i,j)$。需要预处理该点往前最长可能的连续段的长度 $pre_{i,j}$。若 $pre_{i,j}k$ 连续段的,但是这些连续段在之前就已经被减去了,所以需要加上 $f(i-len,j)$。时间复杂度 $\mathcal O(nk)$。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include<iostream> #include<cstdio> using namespace std; const int N=1e5+10,M=100+10,mod=998244353;
template<class T> inline void read(T &x) { x=0;int f=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(f)x=~x+1; } template<class T,class ...T1> inline void read(T &x,T1 &...x1) { read(x),read(x1...); } int n,m,k; int a[N]; int pre[N][M]; int f[N][M],sum[N]; inline int adj(int x){return (x>=mod)?x-mod:x;} inline void upd(int &x,int y){x+=y;x=adj(x);} int main() { read(n,m,k); for(int i=1;i<=n;i++) { read(a[i]); if(~a[i])pre[i][a[i]]=pre[i-1][a[i]]+1; else for(int j=1;j<=m;j++) pre[i][j]=pre[i-1][j]+1; } sum[0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i]!=j&&a[i]!=-1)continue; f[i][j]=sum[i-1]; if(pre[i][j]>=k)upd(f[i][j],adj(-sum[i-k]+f[i-k][j]+mod)); upd(sum[i],f[i][j]); } printf("%d",sum[n]); return 0; }
|