Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC了 0ms 不过代码很粗糙 欢迎各位批评 期待大牛贴出工整清晰的代码我想参考一下

Posted by whj1991 at 2010-08-27 09:57:06 on Problem 1564
//经典搜索

#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator