陪审团
题目 陪审团
思路分析
首先要找差的绝对值最小 然后再在相同的里面找总和更大的那个
差是分布在-400~400之间的 那么优先是选以0为中心 往左往右拓展的那些
而每一个差 都可能有多种选择方式实现（比如对于差-3 绝对值为3 可能选了1 3这两个人 也可能选了2 5这两个人 只要他们的差的绝对值为3即可）
那么这个问题就转变成了背包问题
在前i个人里选j个人 要求差值为k的所有方案
属性是 要和最大的那一个 即max
当然这里比较特殊 有两个不合法的方案 尤其是 在右边集合中 （选i)
（1）当j等于0时 j-1为负数 程序上越界了 实际含义为：从前i个人里选0个人 并且包含第i个人的所有方案 显然也是矛盾的
（2）差值只可能在正负400之间 如果k-(p-d)不在这个范围内了就一定是不合法的 不用管它了
之后就是求背包方案的问题了
思路
用f[i][j][k]表示从前i个人中选j个人且总差为k的所有方案中的总分最大的方案的总分。（好好理一理） 我们维护这个数组，再找出最小的差值v，那么最大分数的方案即为f[n][m][v]所对应的方案。
/！由于分数0——20，那么一个人的差值（p-d）范围在-20——20,20个人总差值就为-400——400。 定一个偏移量base=400，全部加上base即可使总差值变为0——800。！/
代码段落：
输入——维护f数组——找最小差值v——找入选的人——计算人选的两个总分——输出
分段讲解：
A：维护f数组。 对于第i个人，只有选与不选的两种情况。 一、不选，则f[i][j][k]=f[i-1][j][k]。 二、选，那么i需要减少，j（还未入选人数）也要减少，且k（总差值）应减去第i人的差值（p[i]-d[i]）。 由于f表示总分,所以还需要加上第i人的总分（d[i]+p[i]）。 综上，f[i][j][k]=f[i-1][j-1][k-(p[i]-d[i])]+d[i]+p[i]; 注意，应该先判断是否能加入第i人，也就是说要先判断j减去1后会不会小于0， 以及k减去第i人的差值后会不会越界（也就是小于0，或大于最大值800）。 最后从选与不选中选择可行且值最大的方案。
B:找最小差值v。 我们先将v设为0(也就是最理想的情况)。 然后判断，方法是看f[n][m][v+base]和f[n][m][base-v]是否都小于0， 若都小于0，则说明不存在此种情况，则v++，利用while循环找出最小的v值。 此外可能出现base+v和base-v都合法的情况，则需要判断哪一个的总分最大（就是将f值比大小） 将v赋成那个方案所对应的v值（注意加上base）
C：找入选的人。 反过来推。首先从f[i][j][v]开始，(i=n,j=m,这里的v是上面找出来的最小差值加上base)开始， 判断他是由哪一种情况得来（选与不选），若是不选，直接将i--；若选，记录人选，将v减掉该人的差值， 再i--，j--。
相当的复杂……
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=210,M=810,base=400;//往右偏移400 使最小值变成0
int p[N],d[N];
int dp[N][21][M];
int n,m;
int ans[N];
int main()
{
int T=1;
while(cin>>n>>m && (n || m))
{
for(int i=1;i<=n;i++)
cin>>p[i]>>d[i];
memset(dp,-0x3f,sizeof dp);//有多轮数据 进行重置
dp[0][0][base]=0;//从0个人里选0个人 差值是0 也就是base（偏移一下）
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<M;k++){
dp[i][j][k]=dp[i-1][j][k];
//当j等于0时 j-1为负数 程序上越界了 实际含义为：从前i个人里选0个人 并且包含第i个人的所有方案 显然也是矛盾的
if(j<1)
continue;
//差值只可能在正负400之间 如果k-(p-d)不在这个范围内了就一定是不合法的 不用管它了
int t=k-(p[i]-d[i]);
if(t<0 || t>=M)
continue;
//剩下的就都是合法方案了
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][t]+d[i]+p[i]);
}
}
}
//由此一来 所有的状态就都初始化出来了
//现在只要找差的最小的是多少
int v=0;
//若差值为正负v的时候不存在方案 就扩大差值的范围
//这一过程可以理解成 从0开始找 靠近0的是最优的嘛 但是不一定存在这个解
//如果不存在就往两边延升 去找合法的最小的解
//因为一开始就把-400偏移到了0 所以这里可以直接在400处+-v进行这个找最优解的操作
while(dp[n][m][base-v]<0 && dp[n][m][base+v]<0)
v++;
//循环结束自然就找到了那个最小的差值 现在就要找负的和正的两个里面 哪个的和更大
if(dp[n][m][base-v]>dp[n][m][base+v])
v=base-v;
else
v=base+v;
//记录方案
int cnt=0;
int i=n,j=m,k=v;
//再往回做一次状态转移
while(j)//因为要选出m个人 所以没选完就一直做
{
//判断能否不选第i个方案
if(dp[i][j][k]==dp[i-1][j][k])
i--;
else//一定要选i的话
{
ans[cnt++]=i;//把这个方案记下来
//更新状态
k-=(p[i]-d[i]);
i--,j--;
}
}
//要求输出 d的总和 p的总和 以及所有选出来的人
int sp=0,sd=0;
//枚举所有选出来的人 把d，p的和求出来
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);//本来不需要 可能y总偷懒把检测的改了 只能按顺序输出了
for (int i = 0; i < cnt; i ++ )
printf(" %d", ans[i]);
puts("\n");
}
return 0;
}
💬 评论