Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC了 0ms 不过代码很粗糙 欢迎各位批评 期待大牛贴出工整清晰的代码我想参考一下//经典搜索 #include <iostream> using namespace std; int x[13],a[13]; //记录解 int t,n; //n个数可选 int next(int v,int w) { if(w==0) return v+1; else return w+1; } void solve() { cout<<"Sums of "<<t<<":\n"; int i,ns=0,z,count=0,k; for(i=1;i<=n;i++) x[i]=0; x[1]=1; while(x[1]<=n) //最外层循环 x[1]不断累加 { while((a[x[1]]>t)&&(x[1]<=n)) x[1]++; if(x[1]>n) break; //x[1]已敲定 ns=z=a[x[1]]; if(ns==t) //只选了一个数就==t { count++; cout<<a[x[1]]<<endl; while(a[x[1]]==t) //避免重复的一个数解 x[1]++; continue; } for(i=x[1]+1;i<=n;i++) z+=a[i]; if(z<t) //加完所有仍不到 直接结束 break; i=2; while(i>=2) { x[i]=next(x[i-1],x[i]); // cout<<"****"<<x[i]<<endl; while((ns+a[x[i]]<t)&&(x[i]<=n)) { ns+=a[x[i]]; //加完后ns仍小于t i++; x[i]=next(x[i-1],x[i]); } if(ns+a[x[i]]==t) { count++; for(k=1;k<i;k++) cout<<a[x[k]]<<"+"; cout<<a[x[i]]<<endl; //输出完成 求别的解 for(k=x[i]+1;k<=n;k++) //重复的数不再需要 { if(a[k]!=a[x[i]]) break; } if(k>n) { x[i]=0; i--; ns-=a[x[i]]; k=next(x[i-1],x[i]); while(a[k]==a[x[i]]) { x[i]=k; k=next(x[i-1],x[i]); } k--; x[i]=k; } else { k--; x[i]=k; } } else if(x[i]>n) //找到最后一个数仍不满足 { x[i]=0; i--; ns-=a[x[i]]; k=next(x[i-1],x[i]); while(a[k]==a[x[i]]) { x[i]=k; k=next(x[i-1],x[i]); } k--; x[i]=k; } } k=x[1]+1; while(a[k]==a[x[1]]) { x[1]=k; k=x[1]+1; } x[1]=k; } if(count==0) cout<<"NONE\n"; } int main() { cin>>t>>n; while(n) { for(int i=1;i<=n;i++) cin>>a[i]; solve(); cin>>t>>n; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator