| ||||||||||
| 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 | |||||||||
1015的测试数据谁有啊?我的程序,老是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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator