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