之前贪心的想法确实是错误的，比赛的时候数据太水了，过了也就没有想那么多了。如果误导了他人，实在是抱歉。

　　对于每个元素，最坏情况下它只能够到它后面的第9个数字，因为最坏情况下，它后面的四个数字能被它前面的四个数字消掉，这样它就能和原来是它后面的第9个元素相消了，于是我们可以用d[i][st]表示第i个数字，从i开始的10个数字的状态为st时是否可消。之后记忆化搜索即可。

　　状态转移比较简单，如果st的第1位为0，说明这一位已经被消掉,d[i][st]=dp(i+1,next(st))。如果第1为为1，向后连续找至多五个为1的位，比较是否和第一位数字相同，如果相同，就将st的这两位置为0，然后d[i][st]=d(i+1,next(newst)),newst=st&~1&~(1<<k)，其中x[k]==x[i]。next(st)这个函数是求将st传递到下一个位置时的状态，如果n-p<=10，则st=st>>1,否则st=1<<9|st>>1，因为只有当后面数字多于10个时，才会有新的数字加入到状态中。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAXN 1200 5 using namespace std; 6 //1未选,0已选 7 int n, full, x[MAXN], d[MAXN][MAXN]; 8 int nextst(int p, int st) { 9     if (n - p <= 10) return st>>1;10     else return 1<<9|st>>1;11 }12 int dp(int p,int st) {13     if (p == n) return st == 0;14     if (d[p][st]!=-1) return d[p][st];15     d[p][st] = 0;16     //如果第一位为1直接去一位17     if ((st&1) == 0) d[p][st] = dp(p+1, nextst(p, st));18     else {19         int cnt = 0;20         for (int i = 1; i < 10 && cnt < 5; i++) {21             if (1<
        
         << std::min(10, n)) - 1;42         printf("%d\n", dp(0, full));43     }44 }