题目描述(题目难度：困难)
在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。
陪审团是由法官从公民中挑选的。
法官先随机挑选 N NN 个人（编号 1 , 2 1,21,2…,N NN）作为陪审团的候选人，然后再从这 N NN 个人中按照下列方法选出 M MM 人组成陪审团。
首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 0 到 20 之间。
第 i ii 个人的得分分别记为p [ i ] p[i]p[i] 和 d [ i ] d[i]d[i]。
为了公平起见，法官选出的 M MM 个人必须满足：辩方总分 D DD 和控方总分 P PP 的差的绝对值 |D DD−P PP| 最小。
如果选择方法不唯一，那么再从中选择辨控双方总分之和 D + P D+PD+P 最大的方案。
求最终的陪审团获得的辩方总分 D DD、控方总分P PP，以及陪审团人选的编号。
注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含两个整数 N NN 和 M MM。
接下来 N 行，每行包含两个整数 p [ i ] p[i]p[i] 和 d [ i ] d[i]d[i]。
每组测试数据之间隔一个空行。
当输入数据 N NN=0，M MM=0 时，表示结束输入，该数据无需处理。
输出格式
对于每组数据，第一行输出 Jury #C，C 为数据编号，从 1 开始。
第二行输出 Best jury has value P for prosecution and value D for defence:，P PP 为控方总分，D DD 为辩方总分。
第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。
每组数据输出完后，输出一个空行。
数据范围
1≤N NN≤200,
1≤M MM≤20
0≤p [ i ] , d [ i ] p[i],d[i]p[i],d[i]≤20
输入样例：
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
解题报告
一、题意解读
对于每一个人，分析下来其实只有两种选择的，要么能选他，要么不选他。那么咱们就可以向着01背包的方向思考了。
二、DP分析
三、难点剖析
(1)状态转移方程
注意DP分析图中的集合f [ i , j , k ] f[i,j,k]f[i,j,k]所代表的含义，以及所依赖的最大值属性。才能更好的对状态计算中的状态转移方程进行确定。
(2)答案输出
DP环节中计算出所有的总和最大的情况。现在需要做的就是去枚举出差值最小的情况。
从f [ n , m , x x x ] f[n,m,xxx]f[n,m,xxx]中枚举，比如看看0存不存在方案，假如存在，说明差值最小可以是0，再枚举1和-1，紧接着2和-2等等。
假如3和-3都存在差值最小的了，那么此时就要去计算是谁的和更大，选择和更大的作为答案输出。
最后还要求我们把选择的人究竟是谁搞出来，需要咱们反推。也就是琢磨当前这个f [ i , j , k ] f[i,j,k]f[i,j,k]是从左边的状态转移过来的了，还是右边的状态转移过来的了。
找DP问题的方案本质从终点开始反推，当前这个状态是从哪个状态转移过来的。很像一个有向无环图去找当前结点的前一个结点，但是注意当前这个结点可能是多个结点指向过来的。
四、算法流程
参考代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; //因为数组中不能存在负数，所以需要把-400~+400映射到大于等于0的范围内，所以加了400的偏移量 //打分范围是0 ~ 20，最多可以选20个人，搭配起来，就可组成-400 到 400中的任意值 const int N = 210, M = 810,base = 400; int n,m; //n个人中选m个 int p[N],d[N];//存放控方分数的数组p,和存放辩方分数的数组d int f[N][21][M];//第一维是人数，第二维是最多选多少个人，第三维是差值总和 int ans[N]; //存放最后答案的方案数目 int main() { int T = 1; //多组测试数据，直到读到0和0为止 while(scanf("%d %d",&n,&m),n||m) { //读入n个人p和d的值 for(int i = 1; i <= n;i++) scanf("%d %d",&p[i],&d[i]); //初始化f数组,求最大值，所以初始化为负无穷 memset(f,-0x3f,sizeof f); f[0][0][base] = 0;//解决f[0, 0, 0] 这个合法状态 //用f[i][j][k]表示从前i个人中选j个人且总差为k的所有方案中的总分最大的方案的总分 for(int i =1; i <= n;i++) for(int j = 0; j <= m;j++) for(int k = 0; k <= M;k++) { f[i][j][k] = f[i-1][j][k]; //计算差值，用于判断"选第i个人的情况是否存在" int t = k - (p[i] - d[i]); //处理特殊情况 if(t < 0 || t >= M) continue; if(j < 1) continue; f[i][j][k] = max(f[i][j][k],f[i-1][j-1][t]+p[i]+d[i]); } //到这里为止，就处理好了801种情况中总总和最大各自是多少。现在去从中枚举差值最小的情况 int v= 0; //处理最小差值 //base-v 和 base+v 分别代表负数范围和正数范围 //差值在负数范围以及在正数范围内都不存在合理数据的时候，就得去更新这个v while(f[n][m][base-v] < 0 && f[n][m][base+v] < 0) v++; //比较负数范围内的更大还是正数范围内的更大，筛选一个大点的 if(f[n][m][base-v] > f[n][m][base+v]) v = base - v; else v = base +v; //从终点倒着推求方案的过程 int cnt = 0; int i = n,j = m, k = v; //当还没有找够m个可选的人的时候，就继续执行 while(j) { //如果当前方案是从不选择i的情况转移过来的，那么可以直接扣除i if(f[i][j][k] == f[i-1][j][k]) i--; else //否则就是从选择i的情况转移过来的 { ans[cnt++] = i; k -= (p[i]-d[i]); i--, j--; } } int sp = 0, sd = 0; //枚举所有被选中的人，把p的总和以及d的总和求出了 for(int i = 0; i < cnt ;i++) { sp += p[ans[i]]; sd += d[ans[i]]; } //输出答案 printf("Jury #%d\n",T++); //输出数据组号 printf("Best jury has value %d for prosecution and value %d for defence:\n",sp,sd); sort(ans, ans + cnt); //所有选择出来的人的编号 for(int i = 0 ; i < cnt ;i++) printf(" %d",ans[i]); puts("\n"); } return 0; }
