一道很妙的计数DP。
对于样例一：
ababa bacababa aba对于ababa，我们可以删除3位置或5位置。
那么思考何时不用删5位置？显然3位置被删除之后，5位置不用进行删除。
所以现在 i 位置是匹配的位置，当区间[ i-m+1,i-1 ] (m为T的长度 )有一个位置被删了，i位置就可以不用删。
否则i位置必须删除
故可以考虑：dp状态dp[i][0/1]表示：前 i 位已经是合法情况，i位置不删还是删情况下的方案数。
但是这依然无法解决最少的删除次数这一问题。注意到题目无论 |S| 还是 |T|都挺小的，所以我们进一步dp状态。
dp状态dp[i][j][0/1]表示：前 i 位已经是合法情况，此时进行了j次删除操作，i位置不删还是删情况下的方案数。(这个dp状态便是此题的精髓)
接下来是dp转移：
一：i 位置不是匹配位置：dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]（前面是删还是不删不知道，所以都加）
二：i 位置是匹配位置：dp[i][j][0]=∑dp[x][j][1] x∈[ i-m+1,i-1 ],j>0
dp[i][j][1]=dp[i-m][j-1][0]+dp[i-m][j-1][1] j>0
对于∑dp[x][j][1] x∈[ i-m+1,i-1 ]，我们可以多开个sum数组来优化时间复杂度。
则 i 位置是匹配位置：dp[i][j][0]=sum[i-1][j]-sum[i-m][j]
最后考虑：最少的删除次数。根据我们dp状态，dp[n][i][0]+dp[n][i][1]>0时，i 便是可行的删除次数，所以找到第一个i符合方案数>0即可
初始化:dp[0][0][0]=1,注意dp[0][0][1]依旧为0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define popcount __builtin_popcount
const int N=510;
const ll MOD=1e9+7;
const int inf=1e9;
//const ll INF=1e18;
int T,n,m;
bool pos[N];
ll dp[N][N][2],sum[N][N];
string s,t;
inline int read()
{
int x=0,f=1;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();}
return x*f;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>s>>t;
n=s.size();
m=t.size();
s='?'+s;
for(int i=1;i<=n;i++)
if(s.substr(i,m)==t) pos[i+m-1]=1;
dp[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(pos[i])
{
if(j) dp[i][j][1]=(dp[i-m][j-1][0]+dp[i-m][j-1][1])%MOD;
if(j) dp[i][j][0]=(sum[i-1][j]-sum[i-m][j]+MOD)%MOD;
}
else dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
sum[i][j]=(dp[i][j][1]+sum[i-1][j])%MOD;
}
for(int i=0;i<=n;i++)
{
if(dp[n][i][0]+dp[n][i][1])
{
// printf("%d %lld\n",i,(dp[n][i][0]+dp[n][i][1])%MOD);
cout<<i<<" "<<(dp[n][i][0]+dp[n][i][1])%MOD<<"\n";
break;
}
}
for(int i=1;i<=n;i++) pos[i]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j][0]=dp[i][j][1]=sum[i][j]=0;
}
return 0;
}
// if(pos[i]) dp[i][j][1]=dp[i-m][j-1][0]+dp[i-m][j-1][1]
// if(pos[i]) dp[i][j][0]=sum(dp[k][j][1]) k∈[i-m+1,i-1]
// else dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][0]
标签：ch,删除,int,位置,CF1729G,dp,define From： https://www.cnblogs.com/Willette/p/17364495.html