撰写Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit Status Practice POJ 1015
Description
In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.
Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
We will now make this more precise: given a pool of n potential jurors and two values di (the defence’s value) and pi (the prosecution’s value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,…, n} with m elements, then D(J ) = sum(dk) k belong to J
and P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.
For an optimal jury J , the value |D(J) – P(J)| must be minimal. If there are several jurys with minimal |D(J) – P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.
You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.
Input
The input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members.
These values will satisfy 1<=n<=200, 1<=m<=20 and of course m<=n. The following n lines contain the two integers pi and di for i = 1,...,n. A blank line separates each round from the next.
The file ends with a round that has n = m = 0.
Output
For each round output a line containing the number of the jury selection round ('Jury #1', 'Jury #2', etc.).
On the next line print the values D(J ) and P (J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.
Output an empty line after each test case.
Sample Input
4 2
1 2
2 3
4 1
6 2
0 0
Sample Output
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
---------------------
题意：给n组两个一一对应的数，求出m组对应差的总和绝对值的最小值，若有多组，则选择对应和的总和最大的那组。
题解：一拿到这题，感觉有点像LIS类型的题目，都是n个数中，按照一定要求选择m个，但是LIS有着明确的前后关系，而这题没有，所以否定该想法。又想用背包做，但明显并没有物品价值容量，只有物品的个数容量，放弃之。一天以后，熟练打开chrome，百度之。看完题解，发现背包其实已经接近答案了，这题中n和m虽然都不大，但若是排列组合C（200，20）也并不小，所以n，m并不是dp中的关键数据，关键在于数据的最大值，0~20，这样的话，就可以看作背包思想+递推了。
代码：
[cpp]
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int f[30][2000];
int path[30][2000];//>400+400+400
int mid;
int m,n,kase=0;
int d[330];
int p[330];
int v[330];
int s[330];
int a[30];
int main(){
while(scanf("%d%d", &n,&m)==2&&(n||m)){
rep(i,1,n){
scanf("%d%d", &d[i], &p[i]);
v[i]=d[i]-p[i];
s[i]=d[i]+p[i];
}
memset(f,-1,sizeof(f));
memset(path,0,sizeof(path));
mid=m*20;
f[0][mid]=0;
rep(j,0,m-1){
rep(k,0,2*mid){
if(f[j][k]>=0){
rep(i,1,n){
if(f[j][k]+s[i]>f[j+1][k+v[i]]){
int t1=j;
int t2=k;
while(t1>0&&path[t1][t2]!=i){
t2-=v[path[t1][t2]];
t1--;
}
if(t1==0){
f[j+1][k+v[i]]=f[j][k]+s[i];
path[j+1][k+v[i]]=i;
}
}
}
}
}
}
int t1=mid;
int t2=0;
int k;
while(f[m][t1+t2]==-1&&f[m][t1-t2]==-1)t2++;
if(f[m][t1+t2]>f[m][t1-t2])k=t1+t2;
else k=t1-t2;
printf("Jury #%d\n", ++kase);
printf("Best jury has value %d for prosecution and value %d for defence:\n",(f[m][k]+(k-mid))/2, (f[m][k]-(k-mid))/2);
rep(i,1,m){
a[i]=path[m-i+1][k];
k-=v[a[i]];
}
sort(a+1,a+1+m);
rep(i,1,m)printf("%d ", a[i]);
printf("\n\n");
}
return 0;
}
[/cpp]