求解：出牌算法

zyp911 发表于 2013-9-25 22:11
我能想到的办法是
我所有的PowerKey组合后 和 剩下的字符串 重新排序
再来判断 是否可以

powerkey是什么....另外 我认真想了下，如果能消除数量为1的元素（通过顺子），使得剩下的元素至少有2个，那么一定能出完。从这个方向考虑，算法可能会简单点。

这个题本身简单了做，就是回溯，找一个合法组合，剔掉，再递归地搜索剩下的元素中的合法组合，1能替代所有元素也是一样的做法。你认真考虑就从回溯遍历来做，先把第一个问解决了，我觉得你就能自然明白第二个怎么做了。

这不是最基础的DP吗。bool F[I]表示到当前位能不能一次出掉。

状态方程：
F[0]=TRUE, F[1..N-1]=FALSE
F[I]=F[J]（当i,j之间可以出掉） O（n^2)

还是我理解错了？

burning_k 发表于 2013-9-26 02:34
这不是最基础的DP吗。bool F表示到当前位能不能一次出掉。

状态方程：

似乎挺有道理

能尝试写来看看嘛

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAXN 100

int a[MAXN];
bool f[MAXN];

bool test(int j,int i){
        if (j==i) return false;
        if (i-j==1){
                 if (a[j]==a[i]) return true; else return false;
        }
        int tempp[MAXN];
        int num;
        int x=0;
        for (num=j;num<=i;num++){tempp[x++]=a[num];}
        sort(tempp,tempp+x);
        if (tempp[0]==tempp[x-1]) return true;
        if ((i-j==2)&&(tempp[0]==tempp[1]-1)&&(tempp[1]==tempp[2]-1)) return true;
        return false;
}

int main()
{
   int temp;
   int k=0;
   int i,j;
   k=1;
   freopen("in","r",stdin);
        freopen("out","w",stdout);
   while (scanf("%d",&temp)==1){
           a[k++]=temp;
   }
   memset(f,false,sizeof(f));
   f[0]=true;
   for (i=0;i<k;i++)
           for (j=0;j<i;j++){
                   if ((test(j+1,i))&&(f[j])&&(i-j<5)) f[i]=true;
           }
   if (f[--k]) printf("true"); else printf("false");
   return 0;
}