自建网站备案,无锡有哪些做网站的公司,wordpress widget id,合肥网这题在网上看到一个非常容易理解的思路#xff0c;和大家分享一下。 记dp[i][j]为前i个字符删除j个字符后得到不同字符串的数量#xff0c;可以得到以下两个转移方程 dp[i][j1]dp[i][j1]dp[i-1][j] (删除s[i]) dp[i][j]dp[i][j]dp[i-1][j] (不删除s[i]) 如果只用上述式子和大家分享一下。 记dp[i][j]为前i个字符删除j个字符后得到不同字符串的数量可以得到以下两个转移方程 dp[i][j1]dp[i][j1]dp[i-1][j] (删除s[i]) dp[i][j]dp[i][j]dp[i-1][j] (不删除s[i]) 如果只用上述式子是会重复的。比如abcdecf删除cde得到abcf删除dec得到的也是abcf。 所以要删除重复计算的。从当前的i向左扫扫到的第一个与s[i]相同的字符时处理假设为s[k]那么dp[i][j]dp[i][j]-dp[k-1][j-(i-k)]。 #includeiostream
#includecstdio
#includestring.h
#includemath.h
#define maxn 1000005
using namespace std;
typedef long long ll;
char s[maxn];
ll dp[maxn][5];
int main()
{scanf(%s,s1);int lstrlen(s1);dp[0][0]1;for(int i0;il;i){for(int j0;j3;j){if(dp[i-1][j]0)continue;if(j3)dp[i][j1]dp[i-1][j];dp[i][j]dp[i-1][j];for(int ki-1;k1i-kj;k--){if(s[k]s[i]){dp[i][j]-dp[k-1][j-ik];break;//如果有多个因为是从前往后推的所以在前面减过了}}}}printf(%lld\n,dp[l][0]dp[l][1]dp[l][2]dp[l][3]);return 0;
} View Code 转载于:https://www.cnblogs.com/FTA-Macro/p/10472057.html
