| ||||||||||
| 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