比较简单的 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;
}
|