CF578D
这道题还是挺有意思的。
题意简单，就是让你求出与模式串 \(S\) 长度均为 \(len\) 的最长公共子序列为 \(len-1\) 的字符串 \(T\) 的数量。
首先在 \(T\) 固定的情况下求最长公共子序列，就是经典的 dp 式子，不再多说。
那么对于 dp 式 \(dp_{i,j}\) 对 \(dp_{n,n}\) 最大贡献值为 \(min(i,j) + min(n-i,n-j)\)，我们要求这个式子的结果得大于 \(len-1\)，式子推一下发现就是要满足 \(|i-j| \le 1\)，那么对于固定的 \(i\)，有效的 \(dp\) 值只有 \(3\) 个，即 \(i-1\)，\(i\)，\(i+1\)，而且 \(dp\) 值必须得是 \((i-2,i-1)\)，\((i-1,i)\)，\((i-1,i)\)，那么就直接 \(2^3\) 维护即可。
dp of dp 题目
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e18,N=1e5+5;
int n,m;
char s[N];
int dp[N][8],a[N];
int pre[3],now[3]; //i-1 i i+1
signed main(){
n=read(),m=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
for(int i=1;i<=m;i++){
int nxt=1;
if(i==a[1]) nxt+=2;
if(i==a[1]||i==a[2]) nxt+=4;
dp[1][nxt]++;
}
for(int i=1;i<n;i++) for(int j=0;j<8;j++){
if(!dp[i][j]) continue;
for(int k=1;k<=m;k++){
pre[0]=(i-2)+(j&1);
pre[1]=(i-1)+((j>>1)&1);
pre[2]=(i-1)+((j>>2)&1);
now[0]=max(pre[1],pre[0]+(a[i]==k));
now[1]=max({now[0],pre[2],pre[1]+(a[i+1]==k)});
now[2]=max({now[1],pre[2]+(a[i+2]==k)});
if(now[0]<i-1||now[1]<i||now[2]<i) continue;
int nxt=0;
if(now[0]==i) nxt+=1;
if(now[1]==i+1) nxt+=2;
if(now[2]==i+1) nxt+=4;
dp[i+1][nxt]+=dp[i][j];
}
}
cout<<dp[n][0]+dp[n][1]<<'\n';
}