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

Posted by CVking at 2014-09-16 21:24:58 on Problem 1564
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
#include <string>
#include <stack>  
#include <queue>
#include <list>
using namespace std;
int t,n,a[20],temp[20];				//temp数组是为了存放对应答案
bool flag;
void DFS(int sum,int pos,int cnt)
{
	if(sum==t){
		printf("%d",temp[0]);	
		for(int i=1;i<cnt;i++)
			printf("+%d",temp[i]);
		printf("\n");
		flag=true;					//判断是否有解
	}else{
		for(int j=pos;j<n;j++){
			if(j==pos || a[j]!=a[j-1]){			//此处 a[j]!=a[j-1]是为了避免重复
				temp[cnt]=a[j];
				DFS(sum+a[j],j+1,cnt+1);		//总是写不好一个递归
			}
		}
	}
}
int main()
{    
    while(scanf("%d %d",&t,&n)==2)
    {
		if(t==0 && n==0)
			break;
        for(int i=0;i<n;i++)
          scanf("%d",&a[i]);
		flag=false;
		printf("Sums of %d:\n",t);
		DFS(0,0,0);
		if(!flag)
			printf("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