plaese kill me. && don't forget me.
题目描述
给定 \(n\) 个字符串 \(s_i\) 只包含 0,1,2，现在要捏一个序列 \(A\)，\(s_i\) 表示 \(a_i\) 可以捏成什么。1,2,3 形成环形吊打关系，\(\omega(X)\) 表示序列 \(X\) 最长的吊打子序列，吊打序列指的是对于 \(a_{p_1},\dots,a_{p_k}\) ，除了首位每一位都被前一个吊打。求对于 \(t=1,\dots,n\) 满足 \(\omega(A)=t\) 的 \(X\) 有多少个。
\(n\leq 2000\)
题解
先考虑给定一个序列 \(\omega(A)\) 怎么求，简单 dp，设 \(f[i][0/1/2]\) 表示前 \(i\) 位以 \(0/1/2\) 结尾的最长长度，假设 \(x\) 吊打 \(y\)，\(f[i][y]=\max\{f[j][x]+1\}\)。
发现关心 \(f[i][0/1/2]\)，那么弄更好做的状态 \(g[i][x][y][z]\) 表示前 \(i\) 位以 \(0/1/2\) 结尾的吊打子序列最长为 \(x/y/z\) 的方案数，转移就跟自己和吊打 add1 取 max 就可以啦 qwq
然后到了喜闻乐见的优化环节，题目特性对于 \(x,y,z\) 有类似 \(|x-y|\leq 2\) 的关系，于是乎有用的状态就很少啦，把后两维换成 \(-2\to2\)，第一位加个滚动就可以愉快的 AC 了捏。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2023, P=998244353;
int n, lsy[N][4], ans[N];
int f[2][N][5][5];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=1; i<=n; ++i) {
string s; cin >> s;
for(int j=0; j<s.size(); ++j)
lsy[i][s[j]-'0']=1;
}
f[0][0][2][2]=1;
for(int i=1; i<=n; ++i) {
int u=i%2, v=1-u;
memset(f[u],0,sizeof(f[u]));
for(int j=0; j<i; ++j)
for(int a=0; a<5; ++a)
for(int b=0; b<5; ++b) {
if(!f[v][j][a][b]) continue;
int x=j, y=j+a-2, z=j+b-2, qwq;
if(lsy[i][0]) {
qwq=max(x,z+1);
f[u][qwq][y-qwq+2][z-qwq+2]+=f[v][j][a][b];
f[u][qwq][y-qwq+2][z-qwq+2]%=P;
}
if(lsy[i][1]) {
qwq=max(x+1,y);
f[u][x][qwq-x+2][z-x+2]+=f[v][j][a][b];
f[u][x][qwq-x+2][z-x+2]%=P;
}
if(lsy[i][2]) {
qwq=max(y+1,z);
f[u][x][y-x+2][qwq-x+2]+=f[v][j][a][b];
f[u][x][y-x+2][qwq-x+2]%=P;
}
}
}
for(int i=0; i<=n; ++i)
for(int a=0; a<5; ++a)
for(int b=0; b<5; ++b) {
ans[max(max(i,i+a-2),i+b-2)]+=f[n%2][i][a][b];
ans[max(max(i,i+a-2),i+b-2)]%=P;
}
for(int i=1; i<=n; ++i)
cout << ans[i] << ' ';
return 0;
}