Codeforces|Codeforces Round #349 (Div. 2) C. Reberland Linguistics DP CodeforcesRound#349(Div.2)C.Reberlan

题意：
自己读了半天题，果断没看懂题意，看了题解才明白是这个意思啊。
【Codeforces|Codeforces Round #349 (Div. 2) C. Reberland Linguistics DP】给一个字符串,去掉一个长度至少为5的前缀,剩下的切成长度为2或者3的串,且相邻的串不相同,问,最后可以切成多少个串且分别是什么;
思路：
dp[i][2]==1表示i,i+1形成的串可以满足要求,dp[i][3]==1同理; 再就是转移了;
考虑i位置,长度为2;
(1)如果(i,i+1)与(i+2,i+3)相同,那么只有dp[i+2][3]==1时dp[i][2]=1;
如果(i,i+1)与(i+2,i+3)不同,那么只要dp[i+2][2]==1或者dp[i+2][3]==1时dp[i][2]=1;
(2)如果(i,i+1,i+2)与(i+3,i+4,i+5)相同,只有dp[i+3][2]==1时dp[i][3]=1;
如果不同,那么只要dp[i+3][2]==1或者dp[i+3][3]==1时dp[i][3]=1;
代码

#include #include #include #include #include using namespace std; const int N=1e5+5; bool d[N][4]; int main() { string s; cin>>s; if(s.size()<=6){ printf("0\n"); return 0; } int n=s.size(); d[n][2]=d[n][3]=1; vectorans; for(int i=n-2; i>=5; i--){ string now(s,i,2); string next(s,i+2,2); d[i][2]=(now!=next)&&d[i+2][2]; d[i][2]=d[i][2]||d[i+2][3]; if(d[i][2])ans.push_back(now); if(i==n-2)continue; string now1(s,i,3); string next1(s,i+3,3); d[i][3]=(now1!=next1)&&d[i+3][3]; d[i][3]=d[i][3]||d[i+3][2]; if(d[i][3])ans.push_back(now1); } sort(ans.begin(),ans.end()); int sum=0; ans.push_back(""); for(int i=0; i1; i++) if(ans[i]!=ans[i+1])sum++; cout<"\n"; for(int i=0; i1; i++) if(ans[i]!=ans[i+1])cout<"\n"; return 0; }

转载于:https://www.cnblogs.com/01world/p/5651220.html