锐客网

  1. 首页 > it技术 > >

递推DP|Codeforces 667C Reberland Linguistics (DP)

codeforces递推DP

题意 【递推DP|Codeforces 667C Reberland Linguistics (DP)】给出一个字符串，选出大于4个字符当前缀，然后把后面的字母分成2个或者3个的小字符串，要求每个字母都要包括并且在同一个分词方案里面没有连续的相同小字符串，字典序输出所有可以分出来的小字符串。
思路 刚开始我枚举出所有除去末尾剩一个字母的可能的后缀串，然后WA6了，然后想到有可能会有xxxxxabab这种，然后特判了一下还是WA6,然后想到xxxxxababab这样也不会有ab，然后感觉再特判一下可能还会有奇怪的数据是特判不出来的(比如第六组abcdexyzzzz),就考虑DP，但是DP怎么可能保存下来这个方案的所有字符串呢，然后就在这题的挣扎中GG了。。。赛后我才知道原来是我题意读错了。。。mdzz
it is not allowed to append the same string twice in a row.这句话竟然说的是不能连续出现两次(可恶的twice。。。)，也就是不连续的两个相同字符串是可以的。
然后就可以随便DP了。。。dp[i][2/3]表示从i开头长度为2/3的字符串是否满足条件，然后从后往前推一下，如果和上一个字符串不相同，或者上一个和现在这个选的长度不同那么s.substr(i,2/3)就是合法的，把每个字符串都放入set然后输出就可以了。
代码

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define lowbit(x) ((x)&(-x)) #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1|1 #define MP(a, b) make_pair(a, b) const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const int maxn = 1e5 + 10; const double eps = 1e-8; const double PI = acos(-1.0); typedef pair pii; bool dp[10010][4]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); string s; while (cin >> s) { memset(dp, false, sizeof(dp)); int n = s.length(); dp[n][2] = dp[n][3] = true; set ans; for (int i = n - 2; i > 4; i--) { if ((dp[i+2][2] && s.substr(i, 2) != s.substr(i+2, 2)) || dp[i+2][3]) ans.insert(s.substr(i, 2)), dp[i][2] = true; if ((dp[i+3][3] && s.substr(i, 3) != s.substr(i+3, 3)) || dp[i+3][2]) ans.insert(s.substr(i, 3)), dp[i][3] = true; } cout << ans.size() << endl; for (auto it : ans) cout << it << endl; } return 0; }

    推荐阅读


    上一篇：【堆模拟费用流增广】UOJ455 [UER #8] 雪灾与外卖

    下一篇：【KD树】BZOJ 4154 [Ipsc2015]Generating Synergy