题意:
输入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;
}