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

总是WA,真郁闷,高手麻烦指点一下:

Posted by zhb_msqx at 2007-08-25 10:39:37 on Problem 2184
#include <iostream>
#include <fstream>
using namespace std;

int cnum;
struct cow{
	int smart,funny;
} cows[110];

int totals,totalf;

int cmp(const void *a1,const void *a2){
	cow s=*(cow *)a1;cow t=*(cow *)a2;
	if(s.smart>=0&&s.funny>=0)return -1;
	if(t.smart>=0&&t.smart>=0)return 1;
	return (-s.smart-s.funny+t.smart+t.funny);
}

void increase(int start,int ssum,int fsum){ //ssum是当前的smart的和,fsum是当前funny的和
	if(cows[start].smart>=0&&cows[start].funny>=0&&start<cnum){//两项指数都是正的,直接加入
		increase(start+1,ssum+cows[start].smart,fsum+cows[start].funny);
		return;
	}
	if(cows[start].smart+cows[start].funny<0&&start<cnum){  //总和为负的,直接舍去
		if(ssum+fsum>totals+totalf&&ssum>=0&&fsum>=0){
			totals=ssum;
			totalf=fsum;
		}					
		return;
	}
	if(start==cnum){    //递归到头了
		if(ssum>=0&&fsum>=0){
			if(ssum+fsum>totals+totalf){
				totals=ssum;
				totalf=fsum;
			}
		}
		return;
	}else{
		  //这里的情况,就是总和大于0,但是有一个为负,所以分别考虑添加和舍去
			int curs=ssum+cows[start].smart;
			int curf=fsum+cows[start].funny;
			increase(start+1,curs,curf);
			increase(start+1,ssum,fsum);
	
	}
}
void main(){
//	ifstream cin("data.txt");
	cin>>cnum;
	for(int i=0;i<cnum;i++){
		cin>>cows[i].smart>>cows[i].funny;
	}
	qsort(cows,cnum,sizeof(cows[0]),cmp);  //排序

	totals=-1;totalf=-1;
	increase(0,0,0);   //递归
	if(totals>=0&&totalf>=0&&!(totals==0&&totalf==0)){
		cout<<(totals+totalf)<<endl;
	}else{
		cout<<0<<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