ABC 214E Chain Contestant(状压计数)
Chain Contestant
现在有十个比赛类型,从现在开始要进行N场比赛。N场比赛的类型通过一个字符串S给出,在S串中选择一个子序列S',满足下列要求:在子序列S'中,不能出现非连续的两个相同比赛类型。
请问S串中有多少满足条件的子序列S',答案对998244353取模。
思路:
首先我们可以知道,对一个比赛是可以选或者不选,但是选择一个比赛会受到前面的选择的约束。所以容易可以想到这是一个计数DP问题。我们注意到比赛只有10个类型,这其中必定有深意。本题中对转移的限制就是不能有类似1021的方案,考虑用一个状态来表示一个比赛有没有在前面被选过。思路至此,已经十分明朗,我们可以用\(f[i][j][k]\)表示在前 i 个字符串中,j 是选过的比赛的二进制表示,k 表示最后一次选的是什么。
对于第 i 个字符,我们可以从st上该位为1的状态,且末位为该字符的状态转移过来,也可以从st上该位不为1的状态,且末位字符不为该字符的状态转移过来。对于每个字符本来可以作为子序列的首字符,所以要把对应的状态的方案数++。
代码
通过滚动来节省空间。
const int mod = 998244353;
int n;
char str[1005];
ll f[2][1 << 10][10]; //滚动
int main()
{
scanf("%d%s", &n, str + 1);
int num = str[1] - 'A';
int flag = 0;
f[flag][1 << num][num] = 1;
for(int i = 2; i <= n; i ++)
{
flag ^= 1;
for(int st = 0; st < (1 << 10); st ++)
for(int j = 0; j < 10; j ++)
if(st >> j & 1)
f[flag][st][j] = f[flag ^ 1][st][j];
int x = str[i] - 'A';
f[flag][1 << x][x] ++;
for(int st = 0; st < (1 << 10); st ++) //当前态
{
if(!(st >> x & 1)) continue; //因为是转移后的状态,所以st中的第i位为1
for(int j = 0; j < 10; j ++) //之前的状态。分类讨论转移。
{
if(j == x)
f[flag][st][x] += f[flag ^ 1][st][j];
else
f[flag][st][x] += f[flag ^ 1][st - (1 << x)][j];
f[flag][st][x] %= mod;
}
}
}
ll res = 0;
for(int st = 0; st < (1 << 10); st ++)
for(int j = 0; j < 10; j ++)
res += f[flag][st][j], res %= mod;
printf("%lld\n", res);
}
标签:214E,ABC,比赛,Chain,int,st,flag,Contestant
From: https://www.cnblogs.com/DM11/p/16921619.html