题目的数据量一看就是暴力的解法，直接深搜模拟一下题目的过程就可以了，具体做法可以看看下面的代码。由于忘记把初始输入的数据排序WA了好多次。查错的时候发现一组数据： 9 3 6 10 12 14 16 19 24 26 正确答案应该是 6 0 14 24 26 30 33 而网上的一些AC代码的结果都是 7 0 3 6 10 22 24 26 问题在于题目中的两个约束条件：刻度尽量少和尺子长度尽量短之间的优先级关系，题目里没有明确说清楚。有些代码剪枝时认为“如果超过最大的尺度那么这个解就是不合格的”。但是根据题目意思，应该是M先要保证最小，然后再是ans[M-1]尽量小。不过题目数据比较水，两种都能ac通过。 再提供几个测试数据： 4 1 3 7 11 11 1 2 3 4 5 6 7 8 9 10 11 0 Case 1: 4 0 1 4 11 Case 2: 6 0 1 2 3 7 11
#include<stdio.h> #include<string.h> #include<algorithm> int s[55],depth,vis[55],N,z[10];//z[]表示选中的数 bool sel[1000010]; bool dfs(int bz,int x){ // printf(" - dfs(%d,%d)\n",bz,x); if(x==depth){ // printf(" -> "); // for(int i=0;i<x;i++)printf("%d ",z[i]); // printf("%d\n",s[N]); for(int i=1;i<N;i++)if(!vis[i]){ bool flag=false; for(int j=0;j<x;j++){ if(sel[z[j]+s[i]]){ flag=true;break;}; } if(!flag){ // printf("<= %d([%d])\n",s[i],i); return false; } } return true; }else{ for(int i=bz;i<N;i++)if(!vis[i]){ int t; for(int j=0;j<x;j++)if(!sel[t=z[j]+s[i]]){ vis[i]=1; z[x]=t; sel[t]=1; if(dfs(i+1,x+1))return true; sel[t]=0; vis[i]=0; } } } return false; } int main(){ int cas=1; // freopen("1.in","r",stdin); // freopen("1.txt","w",stdout); while(~scanf("%d",&N),N){ for(int i=1;i<=N;i++) scanf("%d",s+i); std::sort(s+1,s+N+1); sel[s[N]]=1; for(depth=1;depth<=6;depth++){ if(dfs(1,1)){ z[depth]=s[N]; std::sort(z+1,z+depth+1); printf("Case %d:\n%d\n0",cas++,depth+1); for(int i=1;i<=depth;i++)printf(" %d",z[i]); printf("\n",s[N]); break; } } memset(vis,0,sizeof(vis)); memset(sel,0,sizeof(sel)); } return 0; }