题解 UVA323 【Jury Compromise】

· · 题解

这道题很不错，所以写一篇题解吧。

楼上的dalao也说过了，这是一道01背包拔河问题，实际上并不简单的只是01背包拔河。

这道题中物品的属性也有变化，属性不仅仅是要用于拔河的权值，还有另一个属性，就是这道题中的人，每一个人看做一个物品，其p和d值就是用于拔河的权值，而人本身还有一个属性就是体积，一个人就是1，为了满足恰好选m个的要求。

所以正常来说我们的背包应该设成3维，dp[i][j][k]表示前i个人，选了j个人，k=\sum p[i]-d[i] 时最大的\sum p[i]+d[i]

我们可以优化成滚动数组。

这些细节就不在多说了，想说的就是这道题可以在网上看到很多的题解。 但是有些题解并不是正确的。

有些做法是先枚举m，以选择的人划分阶段。然后在dp内部判断是否选择了重复的。再继续dp

大概是这样的。

for(int j=0;j<m;j++){
            for(int k=0;k<=800;k++)
                if(f[j][k]>=0){
                for(int i=1;i<=n;i++)
                (judge.....)
                }

这样的做法是错误的，因为如果以人数作为阶段划分，每次枚举这一阶段要选那个人进去，首先就需要确定这个人之前没有出现过，第一想法肯定是状压，但是网上的做法并不是这样的。而是写了一个find函数，顺着之前走到过的最优解的路径进行查找，看之前有没有选过这个人。从而更新状态。

但是我们可以发现，如果这样强行把需要记录那个人选没选的信息压掉，就出现了后效性，也就是说，如果达到dp[i][j]这个状态，根据上面的方式转移，其背后还隐藏着路径这个状态。

如果存在相同值也可以到达dp[i][j]这个状态，在上面的方案中是不取的。但是问题来了，如果之后的最优解需要当前选择方案中的一个怎么办呢？？

形象点说，当前选了a b c可以到达dp[i][j],同时如果选d e f也可以到达这个状态,如果最终答案是a d e f，但如果程序选的a b c，那么之后的决策中就没有a，也就不会达到a d e f这个状态。

还有一个很相似的例子就是noip2017 的宝藏，很多人的状态都是错的，因为需要考虑路径的长度，但是数据水就过去了。

这道题一样，是需要考虑已经选择的集合的。 如果根据划分人数为状态，就不需要考虑是否选了重复的。

还有一点就是记路径了。如果用滚动数组的方法记路径会发现出现重复了。但是最终的值是对的，但是方案不对。

这是因为倒叙更新状态的话，dp是不会受到影响的，但是路径数组可能会被自己更新，emm

举个例子，比如当前枚举到3，dp[3][50]是由第三个数转移来的。 我们记录rec[3][50]=3,假设3的权值为5，我们找路径就会先找3，然后找dp[2][45],假设rec[2][45]=2.

如果很巧合的我们用3同样更新了dp[2][45]的话，那么rec[2][45]就变成了3，结果最后找路径就出现了重复。

所以考虑用链表存储路径，状态与状态的转移直接把表头继承过去就行了，然后加上当前点。

总之还是需要多体会吧。dp的后效性还是很坑人的。

对了注意一点，要输出两个换行

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxx=430;
const int maxn=2e2+10;

int n,m,tot;
int dp[30][maxx*2],p[maxn],d[maxn],rec[30][maxx*2];
struct line
{
    int to,next;
}edge[maxn*4*maxx];

void add1(int a1,int a2,int b)
{
    edge[++tot].to=b;
    edge[tot].next=rec[a1][a2];
    rec[a1][a2]=tot;
}
void print(int now)
{
    if(!now)return;
    print(edge[now].next);
    cout<<" "<<edge[now].to;
}

int main()
{
    int cnt=0;
    cin>>n>>m;
    while(n!=0&&m!=0)
    {
        cnt++;
        for(int i=1;i<=n;i++)cin>>p[i]>>d[i];
        memset(dp,-0x3f,sizeof(dp));
        memset(rec,0,sizeof(rec));
        dp[0][maxx]=0;
        for(int i=1;i<=n;i++)
            for(int j=m;j>=1;j--)
                for(int k=-400;k<=400;k++)
                {
                    if(dp[j-1][k-(p[i]-d[i])+maxx]<0)continue;
                    if(dp[j-1][k-(p[i]-d[i])+maxx]+p[i]+d[i]>dp[j][k+maxx])
                    {
                        dp[j][k+maxx]=dp[j-1][k-(p[i]-d[i])+maxx]+p[i]+d[i];
                        rec[j][k+maxx]=rec[j-1][k-(p[i]-d[i])+maxx];
                        add1(j,k+maxx,i);
                    }
                }
        int ans=0,id=0,pp=0,dd=0;
        for(int i=0;i<=400;i++)
        {
            ans=dp[m][maxx+i],id=i;
            if(dp[m][maxx-i]>ans)id=-i,ans=dp[m][maxx-i];
            if(ans>=0)break;
        }
        pp=(ans+id)/2;
        dd=(ans-id)/2;
        cout<<"Jury #"<<cnt<<endl;
        cout<<"Best jury has value "<<pp<<" for prosecution and value "<<dd<<" for defence:"<<endl;
        print(rec[m][id+maxx]);
        cout<<endl;
        cout<<endl;
        cin>>n>>m;
    }
    return 0;
}