L3-020 至多删三个字符 （30 分）

题意：

分析：
d p [ i ] [ j ] 表 示 前 i 里 面 删 除 了 j 个 有 多 少 种 方 法 dp[i][j] 表示前i里面删除了j个有多少种方法 dp[i][j]表示前i里面删除了j个有多少种方法
第i个删除或者不删除有两种情况
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j]+dp[i-1][j-1] dp[i][j]=dp[i−1][j]+dp[i−1][j−1]
这样会有重复
例如cc这种，需要去重，怎么去重呢，那就看什么情况多计算了
很显然删除 X…X （… 代表不知道几个字符，X代表相同字符)
X…和 …X时最后剩下的都是X，会有重复
所以 这种情况需要去重复
当我们处理到i，j时，假设前面x处有一个相同字符，那么就用
d p [ i ] [ j ] − = d p [ x − 1 ] [ j − ( i − x ) ] dp[i][j] -= dp[x-1][j-(i-x)] dp[i][j]−=dp[x−1][j−(i−x)]
意思就是删除x到i-1的字符这部分会有重复

参考代码


const int maxn = 1e6+10;
LL dp[maxn][4];
char ar[maxn];
// int ans[maxn];
int main(void)
{
    cin>>(ar+1);
    int n = strlen(ar+1);
   
    dp[0][0] = 1;
    // for(int i = )
    for(int i = 1;i <= n; ++i){
        for(int j = 0;j <= 3; ++j)
            {
                dp[i][j] = dp[i-1][j];
                if(j) dp[i][j] += dp[i-1][j-1];
                for(int k = i-1;k >= 1&&(i-k) <= j; --k){
                    if(ar[k] == ar[i]){
                        dp[i][j] -= dp[k-1][j-(i-k)];
                        break;
                    }
                }
            }
       
    }

    LL ans = 0;
    for(int j = 0;j <= 3; ++j)
        ans += dp[n][j];
    cout<<ans<<endl;
   return 0;
}