L3-020 至多删三个字符

  表示前  个字符删掉  个字符结果有  个。

1. 第 i 个字符不删，前 i - 1 个字符删除掉 j 个再加上当前字符能取到的个数。
2. 第 i 个字符删了，前 i - 1 个字符删除掉 j - 1 个能取到的个数。

这样会有重复的。例如一个字符串 abcdefdxyz，删除 def 和删除 efd 后得到的字符串都是abcdxyz，这时候就要去重了。

根据上面那个例子，可以发现对于一个字符 s[ i ]，如果在 i 之前存在一个 last，使得 s[ last ] = s[ i ]，那么删除 [ last, i - 1 ] 间的字符和删除 [ last + 1, i ] 间的字符其实是重复的。

那么 dp[ i ][ j ] 就要减去这个重复，这个重复可表示为 dp[ last - 1 ][ j - ( i - last ) ]。当然，如果 i 与last 的差大于等于目前的 j，就已经不可能受到影响了。

abcdefdxyz

abcdefdxyz

删去左部分和右部分的情况重复，那么就需要去重。

首先，如果我们已经决定要删去左部分，删除个数为 i - last 个，还需在前 last - 1 个字符种删除 j - (i - last) 个，即 dp[ last - 1 ][ j - ( i - last ) ]。

选择上述去重，而不是选择右部分 dp[ last ][ j - ( i - last ) ]，是因为左部分是已经去重过了，而右部分还存在重复的影响。

#include <iostream>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
const int N = 1e6 + 10;
 
char s[N];
LL dp[N][4];
int vis[30];
 
int main()
{
    scanf("%s", s + 1);
    
    int len = strlen(s + 1), last;
    
    for (int i = 0; i <= len; i++) dp[i][0] = 1;
    
    for (int i = 1; i <= len; i++) {
        
        last = vis[s[i] - 'a'];
        vis[s[i] - 'a'] = i;
        
        for (int j = 1; j <= 3; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            if (last && j - (i - last) >= 0)
                dp[i][j] -= dp[last][j - (i - last)];
        }
    }
    
    printf("%lld\n", dp[len][0] + dp[len][1] + dp[len][2] + dp[len][3]);
    
    return 0;
}