这个问题就很有意思了，他的状态不再是用单变量表示的，要仔细考虑状态的递归。
/****************************************************** **文件名：百炼-2817 **Copyright (c) 2015-2025 OrdinaryCrazy **创建人：OrdinaryCrazy **日期：20170806 **描述：百炼2817参考答案 **版本：1.0 ******************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> int n,sticks[64],used[64]; int compare(const void* a,const void* b) { return *(int*)b - *(int*)a; } /******************************************************* 首先，对于最小的木棒长度 1，他能整除总长度 2，他比最长的小木棒长 所以我们需要枚举从最长的小木棒长到总长度的所有长度，直到找到一个可行的长度 那么对于一个长度，我们判断它是否可行的方法就是逆推，假如就是这个长度，看能不能分出这么多的小木棍 递归状态f(k,left,len,n) k-还需要切多少个小木棒 left-现在在切的那根还剩多少 len-木棒长度 n-还有多少根完整的木棒 当然正推也是可以的： k-还剩多少个小木棒 left-现在在拼的那根还剩多少 len-木棒长度 n-还有多少根需要拼的木棒 *********************************************************/ /***************************************************** **函数名：solve **输入：k-使用的小木棒数目 left-未拼完的木棒的长度 len-正在尝试的木棒长度 num-完整的木棒需要多少根 **输出：如果能做到，返回1；否则返回0； **功能：判断用k根小木棍能否拼出长度为len的木棒num根+一个长度为left的未拼完木棒 **作者：OrdinaryCrazy **日期：20170807 **版本：1.0 ******************************************************/ int solve(int k,int left,int len,int num) { if(k == 0 && left == 0 && num == 0) return 1;//没有小木棒，也不需要拼大木棒和未拼完木棒，当然是可以的啦 if(left == 0)//已经没有未拼完木棒了，那就拿根新的拼 { left = len; num--; } int i; for(i = 0;i < n;i++)//现在我们来寻找达到这种状态，最后一根拼上去的木棍是哪一根 { if(used[i]) continue;//前面用过了 if(sticks[i] > left) continue;//这肯定不是最后一个上去的 used[i] = 1;//这一根有可能 if(solve(k - 1,left - sticks[i],len,num)) return 1;//如果认为这一根是当前最后一根拼上去的，而且剩余的木棒可以完成最终的目的，那么这条路就是可行的 used[i] = 0;//如果这条路不可行，而且这根木棒是未评完木棒上的第一根或最后一根，那么比他小的情况也就不用考虑了 //这是因为如果是第一根，它放上去不行，那么首先，它是肯定要放上去的，无论放在哪一根，都可以看做第一根， //也就是说它早晚要憋死一根木棍，你前面做再多的尝试，最后都是不行；如果是最后一根，同理。 if(sticks[i] == left || left == len) break; } return 0; } int main() { int i; scanf("%d",&n); while(n) { int sum = 0;//所有木棍的总长度 memset(used,0,sizeof(used)); for(i = 0;i < n;i++) { scanf("%d",&sticks[i]); sum += sticks[i]; } qsort(sticks,n,sizeof(int),compare); for(i = sticks[0]; i <= sum; i ++) { if(sum % i) continue; if(solve(n,0,i,sum / i)) { printf("%d\n",i); break; } } scanf("%d",&n); } return 0; }
