| ||||||||||
| 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 | |||||||||
Re:声明:此题Special Judge没有任何问题In Reply To:声明:此题Special Judge没有任何问题 Posted by:PKU_linshu at 2011-03-04 15:08:36 请把我的这段程序检查一下吗,好么?我测试了很多都正确,谢谢您了。
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
using namespace std;
int mat[202][22];
int mat_res[202][22];
int mat_mem_d[202][22];
int mat_mem_p[202][22];
int mat_mem_dir[202][22];
int ar_res[202];
int ar_d[202];
int ar_p[202];
int main()
{
int num_case = 0;
while(true)
{
num_case++;
int num_total,num_need;
cin>>num_total>>num_need;
if (num_total == 0 && num_need == 0)
{
return 0;
}
for(int cnt=1;cnt<=num_total;cnt++)
{
int a,b;
cin>>ar_d[cnt]>>ar_p[cnt];
}
mat[1][1] = ar_d[1] - ar_p[1];
mat_mem_d[1][1] = ar_d[1];
mat_mem_p[1][1] = ar_p[1];
for(int cnt_n=1;cnt_n<=num_total;cnt_n++)
{
for(int cnt_m=1;cnt_m<=num_need;cnt_m++)
{
if (cnt_n == cnt_m)
{
mat_res[cnt_n][cnt_m] = 1;
mat_mem_d[cnt_n][cnt_m] = mat_mem_d[cnt_n-1][cnt_m-1] + ar_d[cnt_n];
mat_mem_p[cnt_n][cnt_m] = mat_mem_p[cnt_n-1][cnt_m-1] + ar_p[cnt_n];
mat[cnt_n][cnt_m] = mat[cnt_n-1][cnt_m-1] + ar_d[cnt_m] - ar_p[cnt_m];
}
else if (cnt_n < cnt_m)
{
mat_res[cnt_n][cnt_m] = 0;
mat_mem_d[cnt_n][cnt_m] = 0;
mat_mem_p[cnt_n][cnt_m] = 0;
mat[cnt_n][cnt_m] = 0;
}
else
{
if (labs(mat[cnt_n-1][cnt_m]) == labs(mat[cnt_n-1][cnt_m-1] + ar_d[cnt_n] - ar_p[cnt_n]))
{
if (mat_mem_d[cnt_n-1][cnt_m] + mat_mem_p[cnt_n-1][cnt_m] > mat_mem_d[cnt_n-1][cnt_m-1] + mat_mem_p[cnt_n-1][cnt_m-1] + ar_d[cnt_n] + ar_p[cnt_n])
{
mat_res[cnt_n][cnt_m] = 0;
mat[cnt_n][cnt_m] = mat[cnt_n-1][cnt_m];
mat_mem_d[cnt_n][cnt_m] = mat_mem_d[cnt_n-1][cnt_m];
mat_mem_p[cnt_n][cnt_m] = mat_mem_p[cnt_n-1][cnt_m];
}
else
{
mat_res[cnt_n][cnt_m] = 1;
mat[cnt_n][cnt_m] = mat[cnt_n-1][cnt_m-1] + ar_d[cnt_n] - ar_p[cnt_n];
mat_mem_d[cnt_n][cnt_m] = mat_mem_d[cnt_n-1][cnt_m-1] + ar_d[cnt_n];
mat_mem_p[cnt_n][cnt_m] = mat_mem_p[cnt_n-1][cnt_m-1] + ar_p[cnt_n];
}
}
else if (labs(mat[cnt_n-1][cnt_m]) < labs(mat[cnt_n-1][cnt_m-1] + ar_d[cnt_n] - ar_p[cnt_n]))
{
mat_res[cnt_n][cnt_m] = 0;
mat[cnt_n][cnt_m] = mat[cnt_n-1][cnt_m];
mat_mem_d[cnt_n][cnt_m] = mat_mem_d[cnt_n-1][cnt_m];
mat_mem_p[cnt_n][cnt_m] = mat_mem_p[cnt_n-1][cnt_m];
}
else
{
mat_res[cnt_n][cnt_m] = 1;
mat[cnt_n][cnt_m] = mat[cnt_n-1][cnt_m-1] + ar_d[cnt_n] - ar_p[cnt_n];
mat_mem_d[cnt_n][cnt_m] = mat_mem_d[cnt_n-1][cnt_m-1] + ar_d[cnt_n];
mat_mem_p[cnt_n][cnt_m] = mat_mem_p[cnt_n-1][cnt_m-1] + ar_p[cnt_n];
}
}
}
}
cout<<"Jury #"<<num_case<<endl;
cout<<"Best jury has value "<<mat_mem_d[num_total][num_need]<<" for prosecution and value "<<mat_mem_p[num_total][num_need]<<" for defence:"<<endl ;
int out_res =0;
int out_m = num_need;
int out_n = num_total;
while(out_m)
{
if (mat_res[out_n][out_m] == 1)
{
ar_res[out_m] = out_n;
out_n--;
out_m--;
}
else
{
out_n--;
}
}
sort(ar_res+1,ar_res+1+num_need);
for(int cnt=1;cnt<=num_need;cnt++)
{
cout<<" "<<ar_res[cnt];
}
cout<<endl<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator