| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
总是WA,真郁闷,高手麻烦指点一下:#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator