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

1015的测试数据谁有啊?

Posted by alazyrabbit at 2008-11-16 18:36:17
我的程序,老是WA,不知道哪个数据过不了:
#include <iostream>
using namespace std;
int a[200],b[200],c[200],d[200],e[21][801],f[21][801];
int m,n;
bool hasx(int x,int j,int y){
	while(true){
		if(e[j][y]==-1)return false;
		if(f[j][y]==x)return true;
		int k=f[j][y];
		y=y-c[k];
		if(y<0||y>800)return false;
		j--;
		if(j<0) return false;
	}
}
int main(){
	freopen("in.txt","r",stdin);
	int i,j,x,y,k,t;
	t=1;
	while(cin>>n>>m&&n&&m){
		for(i=0;i<n;i++){
			cin>>a[i]>>b[i];
			c[i]=a[i]-b[i];
			d[i]=a[i]+b[i];
		}
		for(i=0;i<801;i++){
			e[0][i]=-1;
			f[0][i]=-1;
		}
		e[0][400]=0;
		for(j=1;j<=m;j++){
			for(y=-400;y<=400;y++){
				k=-401;
				for(x=0;x<n;x++){
					if(y-c[x]+400>=0&&y-c[x]+400<801&&e[j-1][y-c[x]+400]!=-1&&e[j-1][y-c[x]+400]+d[x]>k&&!hasx(x,j-1,y-c[x]+400)){
						k=e[j][y+400]=e[j-1][y-c[x]+400]+d[x];
						f[j][y+400]=x;
					}
				}
				if(k==-401){
					e[j][y+400]=-1;
					f[j][y+400]=-1;
				}
			}
		}
		cout<<"Jury #"<<t<<endl;
		for(i=0;i<=400;i++){
			if(e[m][i+400]!=-1){
				k=i+400;
				break;
			}
			else if(e[m][400-i]!=-1){
				k=400-i;
				break;
			}
		}
		int s[200];
		for(i=0;i<n;i++){
			if(hasx(i,m,k))
				s[i]=1;
			else
				s[i]=0;
		}
		int p=0,q=0;
		for(i=0;i<n;i++){
			if(s[i]==1){
				p+=a[i];
				q+=b[i];
			}
		}
		cout<<"Best jury has value "<<p<<" for prosecution and value "<<q<<" for defence:"<<endl;
		for(i=0;i<n;i++){
			if(s[i]==1)
				cout<<" "<<i+1;
		}
		cout<<endl<<endl;
		t++;
	}
	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