题目链接：http://codeforces.com/problemset/problem/666/A
题目大意：给你一个字符串， 去掉前五个字符， 剩下的字符2 || 3 长度的取， 不能连续2次取相同的， 问这样的取法能取多少组字符
思路：从后往前取，dp[i] 表示 i 以后的字符能合法的取完，每取一次判断后一个是否和他相同， 不相同说明可取， 还有一种情况是abbabba , abb后面还是abb , 但后面可以是
abb|ab|ba|这样的取法， 所以要判断dp[i + 5] 是否为true
1 #include <iostream> 2 #include <cstring> 3 #include <set> 4 #include <cstdio> 5 #include <algorithm> 6 using namespace std; 7 8 char s[10005], a[5], b[5]; 9 int dp[10005]; 10 set <string> p; 11 12 int main() 13 { 14 scanf("%s", s + 1); 15 int len = strlen(s + 1); 16 memset(dp, 0, sizeof(dp)); 17 dp[len + 1] = 1; 18 for(int i = len - 1; i > 5; i--) 19 { 20 if(dp[i + 2]) 21 { 22 if(dp[i + 5]) 23 { 24 dp[i] = 1; 25 26 p.insert(a); 27 } 28 a[0] = s[i], a[1] = s[i + 1], a[2] = ' '; 29 if(dp[i + 4]) 30 { 31 b[0] = s[i + 2], b[1] = s[i + 3], b[2] = ' '; 32 if(strcmp(a, b)){ 33 //cout << a << dp[i + 4] << b<< endl; 34 dp[i] = 1; 35 p.insert(a); 36 } 37 } 38 else 39 { 40 dp[i] = 1; 41 p.insert(a); 42 } 43 } 44 if(dp[i + 3]) 45 { 46 if(dp[i + 5]) 47 { 48 dp[i] = 1; 49 p.insert(a); 50 } 51 a[0] = s[i], a[1] = s[i + 1], a[2] = s[i + 2], a[3] = ' '; 52 if(dp[i + 6]) 53 { 54 b[0] = s[i + 3], b[1] = s[i + 4], b[2] = s[i + 5], b[3] = ' '; 55 if(strcmp(a, b)) 56 { 57 dp[i] = 1; 58 p.insert(a); 59 } 60 } 61 else 62 { 63 dp[i] = 1; 64 p.insert(a); 65 } 66 } 67 } 68 printf("%d ", p.size()); 69 //auto it = p.begin(); 70 set <string>::iterator it = p.begin(); 71 for( ; it != p.end() ; it++) 72 cout << *it <<endl; 73 return 0; 74 }