Jury Compromise

K - Jury Compromise

参考：ACM POJ 1015 Jury Compromise（陪审团的人选，动态规划题，难）

说实话真有点难想，用一个DP[i][j]来表示在选取i个人，辩控差为j（j值已做些许处理）时辩控总分的最大值，用三个for循环来更新这个值。具体思路还是看参考博客吧....

优先队列默认top()是最大值，如果写成priority_queue<int,vector<int>,greater<int> > top()则为最小值

代码：

// Created by CAD on 2019/10/30.

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#define mst(name, value) memset(name,value,sizeof(name))

using namespace std;

int dp[25][805],pre[25][805];

struct score{

    int a,b;

}p[205];

priority_queue<int,vector<int>,greater<int> > q;

void print(int m,int n)

{

    if(!pre[m][n]) return ;

    print(m-1,n-(p[pre[m][n]].a-p[pre[m][n]].b));

    q.push(pre[m][n]);

}

int main()

{

//    FOPEN;

    ios::sync_with_stdio(false);

    cin.tie(0);

    int m,n;

    int Case=0;

    while(cin>>n>>m,m|n)

    {

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

            cin>>p[i].a>>p[i].b;

        mst(dp,-1);

        mst(pre,0);

        int full=m*20;

        dp[0][full]=0;

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

            for(int j=0;j<=full*2;++j)

                if(dp[i][j]>=0)

                    for(int k=1;k<=n;++k)

                    {

                        if(dp[i][j]+p[k].a+p[k].b>dp[i+1][j+p[k].a-p[k].b])

                        {

                            int a=i,b=j;

                            while(a>0&&pre[a][b]!=k)

                                b-=(p[pre[a][b]].a-p[pre[a][b]].b),a--;

                            if(!a)

                                dp[i+1][j+p[k].a-p[k].b]=dp[i][j]+p[k].a+p[k].b,

                                pre[i+1][j+p[k].a-p[k].b]=k;

                        }

                    }

        int temp=0;

        while(dp[m][full+temp]<0&&dp[m][full-temp]<0) temp++;

        if(dp[m][full+temp]>dp[m][full-temp])   temp+=full;

        else temp=full-temp;

        cout<<"Jury #"<<++Case<<endl;

        cout<<"Best jury has value "<< (temp-full+dp[m][temp])/2 <<

        " for prosecution and value "<<(dp[m][temp]-temp+full)/2<<" for defence: "<<endl;

        print(m,temp);

        while(!q.empty())

            cout<<" "<<q.top(),q.pop();

        cout<<endl<<endl;

    }

    return 0;

}

巴特西

Jury Compromise

K - Jury Compromise

最新文章

热门文章