https://www.acwing.com/problem/content/282/
我们把每一个人看成一个物品,绝对值比较讨厌,我们先无视它,这样他的花费就是一个备选人员以及它的pd差值,他的贡献也就是p+d的值,想到了这一点,接下来的问题就是01背包了。
最后我们从基准值开始同时往左右搜,这样也就符合了绝对值min为第一优先,max为第二优先的条件。
小小总结一下:一般我们都是为了求什么当作DP的目标值,而这里由于绝对值的存在以及两重条件,我们可以把其中一个条件设为状态,这里p-d的绝对值比较难弄,于是我们把它拆开并设置为状态,而p+d就是DP的目标值。整体思路还是很有启发意义的。
具体细节见代码
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 210, M = 810, base = 400;
int n, m;
int p[N], d[N];
int f[N][21][M];//f[i][j][k]表示到了第i人,选了j个,d-p总和为k的d+pmax
int ans[N];
int main(){int T = 1;while (scanf("%d%d", &n, &m), n || m){for (int i=1;i<=n;i++) scanf("%d%d",&p[i],&d[i]);memset(f, -0x3f, sizeof f);f[0][0][base]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=M;k++){if(j>i) continue;f[i][j][k] = f[i - 1][j][k];if (j<1) continue;int x=p[i]-d[i];if(k-x<0||k-x>800) continue;f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-x]+d[i]+p[i]);}}}int v=0;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;while(j){if(f[i][j][k]==f[i-1][j][k]){i--;}else{ans[cnt++]=i;k-=(p[i] - d[i]);j--;i--;}}int sp = 0, sd = 0;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");}
}