Codeforces 667C Reberland Linguistics 【dp】简单基础经典dp

参考：http://www.cnblogs.com/qscqesze/p/5448085.html
题意
【Codeforces 667C Reberland Linguistics 【dp】】给出一个字符串，选出大于4个字符当前缀，然后把后面的字母分成2个或者3个的小字符串，要求每个字母都要包括并且在同一个分词方案里面没有连续的相同小字符串，字典序输出所有可以分出来的小字符串。

思路：考虑dp dp[i][0]表示处理到第i个字符，截取(i, i + 2)是否可行； dp[i][1]表示处理到第i个字符，截取(i, i + 3)是否可行；倒着跑一遍就可以了。

#include #include #include #include #include #include #include #include #define CLR(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long LL; typedef pair pii; const int MAXN = 1e5 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; set ans; set :: iterator it; string str; bool dp[MAXN][2]; int main() { while(cin >> str) { ans.clear(); CLR(dp, 0); int len = str.size(); for(int i = len-1; i >= 5; --i) { if(i + 2 == len) { dp[i][0] = true; ans.insert(str.substr(i, 2)); continue; } if(i + 3 == len) { dp[i][1] = true; ans.insert(str.substr(i, 3)); continue; } if(dp[i+2][1] || (dp[i+2][0] && str.substr(i, 2) != str.substr(i + 2, 2))) { dp[i][0] = true; ans.insert(str.substr(i, 2)); } if(dp[i+3][0] || (dp[i+3][1] && str.substr(i, 3) != str.substr(i + 3, 3))) { dp[i][1] = true; ans.insert(str.substr(i, 3)); } } cout << ans.size() << endl; for(it = ans.begin(); it != ans.end(); ++it) { cout << *it << endl; } } return 0; }