L3-020 至多删三个字符 题解(dp求不重复子序列)

题目链接

题目大意

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中\(3\)个字符，结果可能有多少种不同的字符串？

题目思路

以前写过类似的但是忘了。。。

设\(dp[i][j]\)为前i个字符构造长度为j的不同子序列长度

显然\(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]\)

就是选和不选第\(i\)个字符的问题

但是会有重复

假设我们之前有个序列是\(staxya\)，那么如果我们现在选的是\(i=6,j=2\)的情况，如果我们直接按照上面

计算我们就会选择前\(5\)个选\(1\)个字母和\(a\)组合，会出现\(sa,ta\)这种情况，还会选择直接前面\(5\)个数直接组成\(2\)个

字母的情况。那么又会计算到\(sa,ta\)这种情况，那么多出来的部分是不是就是选定最近出现的位置并且保

证这个字母必选的前提下，去前面再选\(j-1\)个字母呢，好了到这里我们就吧全部的问题解决了。

你每一维只要记录\(dp[i][i-3],dp[i][i-2],dp[i][i-1],dp[i][i]\)

然后你可以把\(dp[i][j]\)的第二维映射成\(dp[i][i-j]\)就可以完美解决问题了

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug printf("\n I am here\n");
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=233;
const double eps=1e-6;
const ll INF=0x3f3f3f3f3f3f3f3f;
char s[maxn];
int last[30];
ll dp[maxn][5];
int id(int x,int y){
    int ans=x-y;
    if(ans<0) ans=4;
    return ans;
}
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    dp[0][0]=1;
    for(int i=1;i<=len;i++){
        int x=s[i]-‘a‘+1;
        for(int j=max(i-3,0);j<=i;j++){
            dp[i][id(i,j)]=dp[i-1][id(i-1,j)]+dp[i-1][id(i-1,j-1)];
            if(last[x]){
                dp[i][id(i,j)]-=dp[last[x]-1][id(last[x]-1,j-1)];
            }
        }
        last[x]=i;
    }
    ll ans=0;
    for(int j=max(len-3,1);j<=len;j++){
        ans+=dp[len][id(len,j)];
    }
    printf("%lld\n",ans);
    return 0;
}

L3-020 至多删三个字符 题解(dp求不重复子序列)

原文：https://www.cnblogs.com/hunxuewangzi/p/14705153.html