AOJ2285 Anipero

問題リンク Anipero

• 解法

DPです。dp表をシークレット用とスタンダード用の2つ用意します。
dp[i][x][L]: i番目までのアイドルに対して、費用Lを使ってx人雇う時の最大満足度
とすれば解けます。
この表を2つ作ったら、費用L (L <= LIMIT)だけ使ってスタンダードアイドルをx人( X <= x )雇うとした時、得られる満足度は
dp_standard[M-1][x][L] + max( dp_secret[N-1][1][LIMIT-L], dp_secret[N-1][2][LIMIT-L])
と求まります。あとは、これを最大化するL, xの組み合わせを見つけるだけです。

• ソース

import java.util.Scanner;

//Anipero
public class AOJ2285 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int L = sc.nextInt(), n = sc.nextInt(), m = sc.nextInt(), X = sc.nextInt();
			if((L|n|m|X)==0)break;
			int[] e1 = new int[n], s1 = new int[n];
			for(int i=0;i<n;i++){
				sc.next(); e1[i] = sc.nextInt(); s1[i] = sc.nextInt();
			}
			int[] e2 = new int[m], s2 = new int[m];
			for(int i=0;i<m;i++){
				sc.next(); e2[i] = sc.nextInt(); s2[i] = sc.nextInt();
			}
			int[][][] dp1 = new int[n][3][L+1];
			//-1: 実現不可能のマーク
			for(int i=0;i<n;i++)for(int x=1;x<=2;x++)for(int l=0;l<=L;l++)dp1[i][x][l] = -1;
			for(int l=e1[0];l<=L;l++)dp1[0][1][l] = s1[0];
			for(int i=1;i<n;i++)for(int x=1;x<=2;x++)for(int l=0;l<=L;l++){
				int max = -1;
				if(l>0)max = dp1[i][x][l-1];
				if(l-e1[i]<0){
					max = Math.max(max, dp1[i-1][x][l]); 
				}
				else {
					if(dp1[i-1][x][l]>=0)max = Math.max(max, dp1[i-1][x][l]);
					if(dp1[i-1][x-1][l-e1[i]]>=0)max = Math.max(max, dp1[i-1][x-1][l-e1[i]]+s1[i]);
				}
				dp1[i][x][l] = max;
			}
			int[][][] dp2 = new int[m][m+1][L+1];
			for(int i=0;i<m;i++)for(int x=1;x<=m;x++)for(int l=0;l<=L;l++)dp2[i][x][l] = -1;
			for(int l=e2[0];l<=L;l++)dp2[0][1][l] = s2[0];
			for(int i=1;i<m;i++)for(int x=1;x<=m;x++)for(int l=0;l<=L;l++){
				int max = -1;
				if(l>0)max = dp2[i][x][l-1];
				if(l-e2[i]<0){
					max = Math.max(max, dp2[i-1][x][l]); 
				}
				else {
					if(dp2[i-1][x][l]>=0)max = Math.max(max, dp2[i-1][x][l]);
					if(dp2[i-1][x-1][l-e2[i]]>=0)max = Math.max(max, dp2[i-1][x-1][l-e2[i]]+s2[i]);
				}
				dp2[i][x][l] = max;
			}
			int max = 0;
			for(int x=X;x<=m;x++)for(int l=0;l<=L;l++){
				if(dp2[m-1][x][l]==-1)continue;
				if(dp1[n-1][1][L-l]==-1&&dp1[n-1][2][L-l]==-1)continue;
				int v = dp2[m-1][x][l] + Math.max(dp1[n-1][1][L-l], dp1[n-1][2][L-l]);
				max = Math.max(max, v);
			}
			System.out.println(max);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2285().run();
	}
}