POJ1015 Jury Compromise(DP)

题意：

输入n组数据，选出m个，每组数据有一个D值和一个P值，要求输入|D-P|的和最小时的D和P和选取的数据下标，如果有相同的，输出|D+P|的和最大的那个。

要点：

真的很难这题，因为相同时要输出和最大的那个，所以我们状态转移方程不能只考虑差最小，而且要将k=|D-P|的和放入转移的量，用DP[i][j][k]表示前j个中选i个的差之和为k时|D+P|的和的最大值。因为k可以是负数，所以加上一个偏移量fix，而且k是没办法状态转移的，所以我们只能一个个搜并且标记，一开始d全为-1，更改后说明可以转移，边界值为d[0][j][fix] = 0，转移的时候一共两个决策：一种是不选当前的人，这样d[i][j][k]=d[i][j-1][k]，等于他前一个的d值；如果选取当前的人，那么要判断选择此人前的d是否不为-1等。

网上有大神想出了二维数组的标准做法，就是d[i][k]说明已经选了i个人，差和为k的最大值，后面用j什么的取筛选。想法非常精妙，可惜是错误的，他的算法会出现如果值相同，路径随机选取的问题。discuss里有大牛发现并改进了，真是厉害。正确做法：点击打开链接

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{int d, p;int s, v;
}pre[205];
int d[25][205][810], path[25][205][810];int main()
{int n, m, count = 0;int i, j, k;while (scanf("%d%d", &n, &m) != EOF){if (n == 0 && m == 0)break;for (i = 1; i <= n; i++){scanf("%d%d", &pre[i].p, &pre[i].d);pre[i].s = pre[i].p + pre[i].d;pre[i].v = pre[i].p - pre[i].d;}memset(d, -1, sizeof(d));memset(path, 0, sizeof(path));int fix = 20 * m;			//为了防止出现负数，加一个偏移量for (i = 0; i <= n; i++)d[0][i][fix] = 0;		//边界值，注意偏移量for (i = 1; i <= m; i++)for (j = i; j <= n;j++)for (k = 0; k <= 2 * fix;k++){d[i][j][k] = d[i][j - 1][k];path[i][j][k] = path[i][j - 1][k];//决策一：不取当前的候选人,直接赋值与下一个比较，如果下一个大就更改，当前大就不用改if (k >= pre[j].v&&k - pre[j].v <= 2 * fix&&d[i - 1][j - 1][k - pre[j].v] >= 0 && d[i - 1][j - 1][k - pre[j].v] + pre[j].s >= d[i][j][k]){//决策二：取当前的候选人d[i][j][k] = d[i - 1][j - 1][k - pre[j].v] + pre[j].s;path[i][j][k] = j;//路径记录，说明选了当前点}}for (k = 0; k <= fix; k++)if (d[m][n][fix - k] >= 0 || d[m][n][fix + k] >= 0)//k为最小辩控差break;int div = d[m][n][fix - k] > d[m][n][fix + k] ? fix - k:fix + k;int D = (d[m][n][div] - div + fix) / 2;//辩方总值 = （辨控和+辨控差-修正值）/2    int P = (d[m][n][div] + div - fix) / 2;//控方总值 = （辨控和-辨控差+修正值）/2    printf("Jury #%d\n", ++count);printf("Best jury has value %d for prosecution and value %d for defence:\n", P, D);int ans[25];int c = path[m][n][div];for (i = div,k = m; k >= 1; k--)//选路径的时候已经是按从小到大了{ans[k] = c;i -= pre[c].v;c = path[k - 1][c - 1][i];}for (i = 1; i <= m; i++)printf(" %d", ans[i]);printf("\n\n");}return 0;
}