剪枝啊剪枝
#include #include #include #include #include #include #include #include #include using namespace std; int vis[70],n,a[70],tmp; bool cmp(int x,int y) { return x>y; } int dfs(int m,int dur) { int i; if(m==0&&dur==0) return 1; if(dur==0) dur=tmp; for(i=0;i =0) { vis[i]=1; if(dfs(m-1,dur-a[i])) return 1; vis[i]=0; if(a[i]==dur||dur==tmp) return 0; //剩余部分dur=a[i]或一节的长度tmp时，上面dfs都没有返回1 说明后面无解 while(a[i+1]==a[i]) i++; //这个就显然啦 } } } return 0; } int main() { int i,s; while(scanf("%d",&n)&&n) { for(i=0,s=0;i