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

DFS AC代码

Posted by 452181625 at 2014-05-14 20:47:21 on Problem 1564
#include<iostream>
#include<algorithm>
using namespace std;
int sum,n,flag;
int numb[1005],ways[1005];
void dfs(int now,int now_sum,int ll)
{
	int i;
	if(now_sum==sum)
	{
		flag=1;
		for(i=1;i<ll-1;i++)
			cout<<ways[i]<<'+';
		cout<<ways[i]<<endl;
		return;
	}
	int last=-1;
	for(i=now+1;i<=n;i++)
	{
		if(last==numb[i]) continue;
		if(now_sum+numb[i]>sum) continue;
		ways[ll]=numb[i];
		last=numb[i];
		dfs(i,now_sum+numb[i],ll+1);
	}
}
int main()
{
	int i;
	while(cin>>sum>>n,sum,n)
	{
		flag=0;
		for(i=1;i<=n;i++)
			cin>>numb[i];
		cout<<"Sums of "<<sum<<':'<<endl;
		dfs(0,0,1);
		if(!flag) cout<<"NONE\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