题目链接：
http://poj.org/problem?id=1015
Jury Compromise
Time Limit: 1000MSMemory Limit: 65536K
#### 问题描述
> 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.
#### 输入
> 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 The file ends with a round that has n = m = 0.
#### 输出
> 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.
####样例输入
> 4 2
> 1 2
> 2 3
> 4 1
> 6 2
> 0 0
样例输出
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
题意
给你n个人，每个人有权值a[i],b[i]，现在要选出m个人，使得abs(sigma(a[i])-sigma(b[i]))最小，如果存在多解，则选sigma(a[i])+sigma(b[i])最大的任意一个。
题解
咋看下dp不能做，因为直接维护abs(sigma(a[i])-sigma(b[i]))这个东西根本不满足子问题具有最优子结构的性质。
但是！我们应该马上注意到数据范围很小，因此我们可以尝试在状态上做些手脚，使这个问题能够用dp来做。
不难发现，如果选m个，那么sigma(a[tt]-b[tt])的范围是[-20*m,20*m]，这并不会很大，所以我们可以定义dp[i][j][k]表示考虑了前i个人，选了j个人，sigma(a[tt]-b[tt])+400=k的情况。然后最后枚举下k就可以啦，也就是我们把最优问题转换成了判定问题，并且能用dp来解决。（当然，还要记得维护下sigma(a[tt]+b[tt])最大。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
bool dp[222][22][888];
int ans[222][22][888];
PII arr[222];
vector<int> lis;
void print(int i,int j,int k){
if(i==0){ return; }
int a=arr[i].X,b=arr[i].Y;
int c=a-b;
if(dp[i-1][j][k]&&dp[i-1][j-1][k-c]){
if(ans[i-1][j][k]>ans[i-1][j-1][k-c]+a+b){
print(i-1,j,k);
}else{
print(i-1,j-1,k-c);
lis.pb(i);
}
}else if(dp[i-1][j][k]){
print(i-1,j,k);
}else if(dp[i-1][j-1][k-c]){
print(i-1,j-1,k-c);
lis.pb(i);
}
}
int main() {
int n,m,kase=0;
while(scf("%d%d",&n,&m)==2&&n) {
lis.clear();
for(int i=1; i<=n; i++) {
scf("%d%d",&arr[i].X,&arr[i].Y);
}
clr(dp,0);
clr(ans,0);
rep(i,0,222) dp[i][0][400]=1;
for(int i=1; i<=n; i++) {
int a=arr[i].X,b=arr[i].Y;
int c=a-b;
for(int j=1; j<=m; j++) {
for(int k=0; k<=800; k++) {
if(k-c>=0&&k-c<=800) {
if(dp[i-1][j][k]&&dp[i-1][j-1][k-c]) {
dp[i][j][k]=1;
ans[i][j][k]=max(ans[i-1][j][k],ans[i-1][j-1][k-c]+a+b);
} else if(dp[i-1][j][k]) {
dp[i][j][k]=1;
ans[i][j][k]=ans[i-1][j][k];
} else if(dp[i-1][j-1][k-c]) {
dp[i][j][k]=1;
//这里a+b漏了，调了好久xrz
ans[i][j][k]=ans[i-1][j-1][k-c]+a+b;
}
} else {
dp[i][j][k]=dp[i-1][j][k];
ans[i][j][k]=ans[i-1][j][k];
}
}
}
}
int Mi=INF,pos=-1,Ma=-1;
for(int i=0; i<=800; i++) {
if(dp[n][m][i]) {
if(Mi>abs(i-400)) {
Mi=abs(i-400);
Ma=ans[n][m][i];
pos=i;
} else if(Mi==abs(i-400)&&ans[n][m][i]>Ma) {
Ma=ans[n][m][i];
pos=i;
}
}
}
print(n,m,pos);
int a=0,b=0;
rep(i,0,lis.sz()){ a+=arr[lis[i]].X,b+=arr[lis[i]].Y; }
prf("Jury #%d\n",++kase);
prf("Best jury has value %d for prosecution and value %d for defence:\n",a,b);
rep(i,0,lis.sz()) prf(" %d",lis[i]); prf("\n\n");
}
return 0;
}
//end-----------------------------------------------------------------------
Notes
数据小，没有最优子问题结构的，可以考虑判定性。