PKU 1015-Jury Compromise

問題概要

翻訳Wikiを参照

解法

動的計画法．
二つの重さの差といくつ取ったかでDP．
現在の最大の重さをメモする．
計算量は800x20x200ぐらい

実装(C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
int a[200],b[200];
short dp_data[21][201][1000];
unsigned char back_data[21][201][1000];
short *dp[21][201];
unsigned char *back[21][201];
int testcase=1;
int main() {
	while(scanf("%d%d",&n,&m),(n|m)){
		for(int i=0;i<n;i++){
			scanf("%d%d",a+i,b+i);
		}
		memset(dp_data,-1,sizeof(dp_data));
		memset(back_data,-1,sizeof(back_data));
		for(int i=0;i<21;i++){
			for(int j=0;j<201;j++){
				dp[i][j]=dp_data[i][j]+500;
				back[i][j]=back_data[i][j]+500;
			}
		}
		dp[0][0][0]=0;
		for(int k=0;k<n;k++){
			for(int i=-420;i<=420;i++){
				for(int j=m;j>=0;j--){
					if(dp[j][k][i]>=0){
						if(dp[j][k+1][i]<dp[j][k][i]){
							dp[j][k+1][i]=dp[j][k][i];
							back[j][k+1][i]=back[j][k][i];
						}
						if(j==m)continue;
						if(dp[j+1][k+1][i+a[k]-b[k]]<dp[j][k][i]+a[k]){
							dp[j+1][k+1][i+a[k]-b[k]]=dp[j][k][i]+a[k];
							back[j+1][k+1][i+a[k]-b[k]]=k;
						}
					}
				}
			}
		}
		for(int i=0;i<610;i++){
			int MAX=-1,R=-1;
			if(dp[m][n][-i]!=-1){
				MAX=max(MAX,dp[m][n][-i]+dp[m][n][-i]+i);
				R=-1;
			}
			if(dp[m][n][i]!=-1){
				if(MAX<dp[m][n][i]+dp[m][n][i]+i){
					MAX=dp[m][n][i]+dp[m][n][i]+i;
					R=1;
				}
			}
			if(MAX!=-1){
				int sum=i*R,now=n;
				vector<int> ans;
					for(int x=m;x>0;x--){
						ans.push_back(back[x][now][sum]);
						int t=back[x][now][sum];
						sum-=a[back[x][now][sum]]-b[back[x][now][sum]];
						now=t;
					}
				cout<<"Jury #"<<testcase++<<endl;
				cout<<"Best jury has value ";
				cout<<dp[m][n][i*R];
				cout<<" for prosecution and value ";
				cout<<dp[m][n][i*R]-i*R;
				cout<<" for defence:"<<endl;
				std::sort(ans.begin(),ans.end());
				for(int i=0;i<(int)ans.size();i++){
					cout<<" "<<ans[i]+1;
				}
				cout<<endl<<endl;
				break;
			}
		}
	}

	return 0;
}