当前位置: 代码迷 >> 综合 >> POJ1015 Jury Compromise(DP)
  详细解决方案

POJ1015 Jury Compromise(DP)

热度:74   发布时间:2024-01-16 13:40:18.0

题意:

输入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里有大牛发现并改进了,真是厉害。正确做法:点击打开链接


15554087 Seasonal 1015 Accepted 32640K 641MS C++ 1748B 2016-05-26 08:24:36
#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;
}