L3-2 至多删三个字符

it2023-07-06  73

主要思路:dp[i][j]表示在前i个字符中删除j个字符是字符串种类数,则dp[i][j]分为两种情况删除第i个字符,不删除第i个字符:dp[i - 1][j],删除第i个字符:dp[i - 1][j - 1],所以dp[i][j = dp[i - 1][j] + dp[i - 1][j - 1],然后再考虑重复情况,以样例举例ababcc删除第1,2个元素ab和删除第2,3个元素ba剩余元素都为abcc,再举一个例子abcade,这时删除abc和删除bca剩余元素都为ade,所以我们应该从k = i - 1个元素开始查询s[k] == s[i]的元素,同时k>=1并且j >= (i - k),因为最多删除j个元素,所以此时dp[i][j] = dp[i][j] - dp[k - 1][j - (i - k)]

AC代码

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <string> #include <cmath> #include <queue> #include <vector> using namespace std; const int N = 1000010; long long f[N][4]; char s[N]; int main(void) { scanf("%s", s + 1); int len = strlen(s + 1); f[0][0] = 1; for(int i = 1; i <= len; i++) { for(int j = 0; j <= 3; j++) { if(j > 0) f[i][j] += f[i - 1][j - 1]; f[i][j] += f[i - 1][j]; for(int k = i - 1; k >= 1 && i - k <= j; k--) { if(s[k] == s[i]) { f[i][j] -= f[k - 1][j - (i - k)]; break; } } } } long long sum = 0; for(int i = 0; i <= 3; i++) sum += f[len][i]; cout << sum << endl; return 0; }```
最新回复(0)