Photo by Johannes Plenio from Pexels Jury Compromise
一道dp题，感觉有一定的难度。
一开始的时候发现它很像是01背包，将每个人看作是一件物品，需要取的人数看作是背包的总容量，求要怎样取物品(选人)才能使得\(\sum p_i-\sum d_i\)最小；同时，如果存在\(\sum p_i-\sum d_i\)相同的情况，则取\(\sum p_i+\sum d_i\)较大的那一种方案。
一开始尝试了这样的写法，
int last=-1;
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
if((dp1[j-1]+abs_(d[i]-p[i])<dp1[j])||(dp1[j-1]+abs_(d[i]-p[i])==dp1[j]&&dp2[j-1]+d[i]+p[i]>dp2[j])){
dp1[j]=dp1[j-1]+abs_(d[i]-p[i]);
dp2[j]=dp2[j-1]+(d[i]+p[i]);
pre[i]=last;
last=i;
}
}
}emmmmm很明显是不行的OTZ
后来又尝试了另一种写法，即是使用一个二维dp数组，参照洛谷P1555的做法来写，将\(\sum p_i+\sum d_i\)固定并对它进行枚举，代码大致长这样：
for(int k=1;k<=n;k++){
for(int i=800;i>=0;i--){
for(int j=m;j>=1;j--){
int temp=dp[i][j];
dp[i][j]=min(dp[i][j],dp[i-d[k]-p[k]][j-1]+abs_(d[k]-p[k]));
if(dp[i][j]!=temp){
pre[k]=last;
last=k;
}
}
}
}但这种做法也不可......但至少固定住一个这一想法是正确的。
正确的做法应该是固定住差，然后求能使和最大的方案。dp[j][k]表示在取j人，差为k的所有方案中，和最大的那个方案的和。对于方案dp[j][k]我们不难发现它是由某个方案dp[j-1][x]递推而来的。我们要找的是这样的一个候选人i：此人在方案dp[j-1][x]中没有被选中，且此人满足\(x+p[i]-d[j]=k\)。找出这个人，并在所有满足要求的dp[j-1][x]中，找到和最大的那一个，从而转移的到dp[j][k]。这题还需要输出被选的人，其实就是记录路径。只需要记录下转移得到dp[j][k]时的候选人i即可。另外，由于计算差的时候可能会产生负数从而影响数组操作，所以要做一定的偏移，保证不会产生负数。因为差值的绝对值不会超过20*m，所以将整个差值可能出现的区间向右偏移20*m即可。还有一点，在计算prosecution sum和defence sum时，因为dp求得的时\(\sum p_i+\sum d_i\)，所以要做一定的处理得到\(\sum p_i\)和\(\sum d_i\)。具体做法是： \[ \sum p_i = \frac{\sum (p_i+d_i) + (\sum p_i - \sum d_i)}{2}\\ \sum d_i = \frac{\sum (p_i+d_i) - (\sum p_i - \sum d_i)}{2} \]
实际操作时还要记得减去偏移把区间移回来
更详细的见注释
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int d[300],p[300];
int dp[30][1000];
int path[30][1000];
int n,m;
vector<int> ans;
//dp[j][k]表示在取j人,差为k的所有方案中,和最大的那个方案的和
int main()
{
int kase=0;
while(scanf("%d %d",&n,&m)!=EOF&&n&&m){
int sumd=0;int sump=0;
mst(dp,-1);
mst(path,0);
for(int i=1;i<=n;i++)
scanf("%d %d",&p[i],&d[i]);
int offset=20*m; //因为差所在的区间为[-20*m,20*m],所以偏移为20*m
dp[0][offset]=0; //相当于dp[0][0]=0
for(int j=0;j<m;j++){ //从1个人推到m个人
for(int k=0;k<=offset*2;k++){ //偏移后,差出现的区间在[0,20*m]
if(dp[j][k]>=0){ //如果该方案存在
for(int i=1;i<=n;i++){ //枚举n个人
if(dp[j][k]+d[i]+p[i]>dp[j+1][k+p[i]-d[i]]){
int tmp1=j;
int tmp2=k;
while(tmp1>0&&path[tmp1][tmp2]!=i){ //检查之前i这个人之前是否出现过
tmp2-=p[path[tmp1][tmp2]]-d[path[tmp1][tmp2]];
tmp1--;
}
if(tmp1==0){ //i没有出现过
dp[j+1][k+p[i]-d[i]]=dp[j][k]+d[i]+p[i];
path[j+1][k+p[i]-d[i]]=i;
}
}
}
}
}
}
int tmp1,tmp2;
tmp1=offset;
tmp2=0;
int maxi=-INF;int tag=0;
while(dp[m][tmp1+tmp2]<0&&dp[m][tmp1-tmp2]<0)
tmp2++;
int sub;
if(dp[m][tmp1+tmp2]>dp[m][tmp1-tmp2])
sub=tmp1+tmp2;
else
sub=tmp1-tmp2;
//从中间开始找第一个可用的方案,对应的差值就是所求最小差值
//然而这是为什么呢......
sump=(dp[m][sub]+(sub-offset))/2;
sumd=(dp[m][sub]-(sub-offset))/2;
printf("Jury #%d\n",++kase);
printf("Best jury has value %d for prosecution and value %d for defence:\n",sump,sumd);
ans.clear();
int j;int i;
for(i=1,j=m;i<=m;i++,j--){ //根据路径找答案
int now=path[j][sub];
ans.push_back(now);
sub-=p[now]-d[now];
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf(" %d",ans[i]);
printf("\n\n");
}
return 0;
}