[Poj 1015] Jury Compromise 解题报告 (完全背包)

题目链接：http://poj.org/problem?id=1015

题目：

题解：

我们考虑设计DP状态(因为这很显然是一个完全背包问题不是吗？)

dp[j][k]表示在外层循环到i时，选了j个人，此时辩方总分和控方总分差值为k的时，辩方和控方的总分的和的最大值

dp[j][k+a[i]-b[i]] = max (dp[j][k + a[i] - b[i]] , dp[j][k] + a[i] + b[i])

因为是完全背包，所以我们需要写一个search函数判断当前转移的状态是否已经选过了i,这样我们需要记录一个d[j][k]数组表示在dp[j][k]的状态是选哪一个人转移过来的，这恰好也是题目要求我们处理出来的

题解其实就是上述部分了

题外话：

我们考虑不写那个search函数，然后把j这一维倒序循环，根据《算法竞赛进阶指南》，这样的做法是可以的，但是笔者尝试之后还做不到，碰到的问题就是假设dp[j][k+a[i]-b[i]]被dp[j-1][k]转移得到，此时我们可以确定dp[j-1][k]这个状态没有选择i这个人。

但是在之后的循环中，dp[j-1][k]可能会被再次更新，我们要是只是统计答案的话这并没有什么影响，但是我们在d数组回溯的时候就会得到错误的转移，因为dp[j-1][k]可能被i更新，于是d[j-1][k]变成了i。补充：但是在我的AC代码里，显然是可以避免这种情况的，因为dp[j-1][k]不可能再被更新

除此之外，我发现i循环放在最外面是不行的。这是为什么？若是有读者知道请在评论区留言。

AC代码（加了search函数）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,fix,time;

int a[],b[],dp[][],d[][],id[];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

bool search(int j,int k,int i)

{

    while (j&&d[j][k]!=i)

    {

        int o=d[j][k];

        k-=a[o]-b[o];

        j--;

    }

    if (j) return false;

    return true;

}

int main()

{

    while ()

    {

        n=read();m=read();

        if (!n) break;

        for (int i=;i<=n;i++)

        {

            a[i]=read();b[i]=read();

        }

        memset(dp,-,sizeof(dp));

        memset(d,,sizeof(d));

        fix=m*;

        dp[][fix]=;

        for (int j=;j<=m;j++)

            for (int k=;k<=fix<<;k++)

                if (dp[j-][k]>=)

                {

                    for (int i=;i<=n;i++)

                        if (dp[j-][k]+a[i]+b[i]>dp[j][k+a[i]-b[i]]&&search(j-,k,i))

                        {

                            dp[j][k+a[i]-b[i]]=dp[j-][k]+a[i]+b[i];

                            //if (j==3&&k+a[i]-b[i]==57&&k==58) printf("sdfs%d\n",d[j-1][k]);

                            d[j][k+a[i]-b[i]]=i;

                            //if (j==2&&k+a[i]-b[i]==58) printf("%d\n",i);

                        }

                }

        int k,div;

        for (int i=;i<=fix;i++)

            if (dp[m][fix-i]!=-||dp[m][fix+i]!=-) {k=i;break;}

            //printf("%d\n",k);

        div=dp[m][fix-k]>dp[m][fix+k]?(fix-k):(fix+k);

        printf("Jury #%d\n",++time);

        printf("Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][div]+div-fix)/,(dp[m][div]-div+fix)/);

        int r=div;

        for (int i=;i<=m;i++)

        {

            id[i]=d[m-i+][r];

            r-=a[id[i]]-b[id[i]];

        }

        sort(id+,id++m);

        for (int i=;i<=m;i++) printf(" %d",id[i]);

        printf("\n\n");

    }

     return ;

}

巴特西

[Poj 1015] Jury Compromise 解题报告 (完全背包)

题目链接：http://poj.org/problem?id=1015

题目：

题解：

题外话：

最新文章

热门文章