Jury Compromise

POJ-1015

推荐几个较好的介绍和理解：https://blog.csdn.net/lyy289065406/article/details/6671105
https://blog.csdn.net/glqac/article/details/22687243
#include<iostream>

#include<algorithm>

#include<cstring>

#include<string>

#include<cstdio>

using namespace std;

const int INF=0X3F3F3F3F;

const int maxn=203;

const int maxm=22;

int n,m;

int d[maxn],p[maxn];//被告和原告

int add[maxn],sub[maxn];//sub[i]表示辩控差也就是p-d

int dp[maxn][maxm][802];//dp[i][j][k]表示从前i个人里面选择j个人，辩控差为k时的最大值// dp[i,j,k]=max{dp[i-1,j,k],dp[i-1,j-1,k-d[i]]+ad[i]}

int path[maxn][maxm][802];

int ans[maxm];

struct node{

    int defence;

    int prosecute;

    int num;

};

int main(){

    int cases=0;

    while(cin>>n>>m&&(n||m)){

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

            cin>>p[i]>>d[i];

            add[i]=p[i]+d[i];

            sub[i]=p[i]-d[i];

        }

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

        int fix=m*20;//表示修正值

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

            dp[i][0][fix]=0;////由于修正了数值，因此dp[i][0][fix]才是真正的dp[i][0][0]

        }

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

            for(int j=1;j<=i&&j<=m;j++){

                for(int k=0;k<=fix*2;k++){

                    dp[i][j][k]=dp[i-1][j][k];

                    path[i][j][k]=path[i-1][j][k];

                    if(k>=sub[i]&&dp[i-1][j-1][k-sub[i]]>=0&&k-sub[i]<=2*fix){

                        if(dp[i-1][j-1][k-sub[i]]+add[i]>dp[i][j][k]){

                            dp[i][j][k]=dp[i-1][j-1][k-sub[i]]+add[i];

                            path[i][j][k]=i;

                        }

                    }

                }

            }

        }

        int diff,k;

        for(k=0;k<=fix;k++){

            if(dp[n][m][fix-k]>=0||dp[n][m][fix+k]>=0){

                break;

            }

        }

        if(dp[n][m][fix-k]>dp[n][m][fix+k]){

            diff=fix-k;

        }else diff=fix+k;

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

        cout<< "Best jury has value ";

        //辩方总值 = （辨控和+辨控差-修正值）/2

		cout<<(dp[n][m][diff]+diff-fix)/2<<" for prosecution and value ";

        //控方总值 = （辨控和-辨控差+修正值）/2

		cout<<(dp[n][m][diff]-diff+fix)/2<<" for defence:"<<endl;

        //类似于背包输出路径

        for (int i=n,j=m,k=diff; j>=1;)

		{

			int p = path[i][j][k] ;

			ans[j] = p;

			k -= sub[p];

			j--;

			i = path[p-1][j][k];//

		}

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

		{

			cout << " " << ans[i];

		}

        cout<<endl<<endl;

    }

    return 0;

}
巴特西

POJ-1015(背包变形+输出路径)

Jury Compromise

POJ-1015

最新文章

热门文章
