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

Re:谁能告诉我怎么样除去重复的

Posted by zhb_msqx at 2007-08-24 19:56:38 on Problem 1564
In Reply To:谁能告诉我怎么样除去重复的 Posted by:6233843 at 2006-07-17 18:13:52
#include <iostream>
#include <fstream>
using namespace std;

int sum;
int sticknum;
int stick[20];

int mark[20];

int solution;

int sols[100][20];     //记录不重复的答案
int slen[100];      //记录第j组答案的长度
int solnum;          //记录不重复的答案的数量


void compute(int start,int cursum){
	for(int i=start;i<sticknum;i++){
		if(mark[i]==0&&stick[i]<=cursum){
			mark[i]=1;
			int tmp=cursum-stick[i];
			if(tmp==0){
				int tt=0;
				for(int j=0;j<sticknum;j++){
						if(mark[j]==1){
							sols[solnum][tt++]=stick[j];
						}
				}
				if(solution==0){   //如果是第一组答案,就直接记录
					slen[solnum]=tt;
					solution++;
					solnum++;
					mark[i]=0;
				}else{
					bool test=false;
					for(int k=0;k<solnum&&!test;k++){    //判断答案是否重复,如果重复就不对solnum加1,否则加1,
						if(slen[k]==tt){     //先判断这两组组答案的长度是否相等,不等就直接判断下一组。
							for(int m=0;m<tt;m++){
								if(sols[k][m]!=sols[solnum][m]){
									break;
								}
							}
							if(m==tt)test=true;      //表示答案完全匹配,这一组答案就可以舍掉了
						}
					}
					if(!test){  //如果答案与前面的都不重复,就对solution+1,solnum+1,
						solution++;
						slen[solnum]=tt;
						solnum++;
					}
				}	
			}else{
				compute(i+1,tmp);
			}
			mark[i]=0;
		}
	}
}



void main(){
//	ifstream cin("data.txt");
	while(1){
		cin>>sum>>sticknum;
		if(sum==0)break;
		memset(stick,0,sizeof(stick));
		memset(mark,0,sizeof(mark));
		memset(sols,0,sizeof(sols));
		memset(slen,0,sizeof(slen));
		solution=0;
		solnum=0;
		for(int i=0;i<sticknum;i++){
			cin>>stick[i];
		}
		cout<<"Sums of "<<sum<<":"<<endl;
		compute(0,sum);
		if(solution==0){
			cout<<"NONE"<<endl;
		}else{
			for(int i=0;i<solnum;i++){
				for(int j=0;j<slen[i]-1;j++)
					cout<<sols[i][j]<<"+";
				cout<<sols[i][j]<<endl;
			}
		}
	}
}

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