AOJ 2285 : Anipero

問題リンク:Anipero | Aizu Online Judge

問題概要:
略

解法：
動的計画法

pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度

pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最大の満足度

という２つの配列を前処理として作っておく
これらを作ったあとは、
・スタンダードアーティストをX人からM人の間で何人選ぶか
・シークレットアーティストを1人、2人のどちらにするか
・スタンダードアーティストに何円使うか
をループで決めてそのなかで得られる最大の満足度を出力する

pre,pre2を作る時は、その金額以下で得られる満足度のほうが大きい場合はそちらをいれる処理をすること

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX_LIMIT 1100
#define MAX 110

using namespace std;

int pre[MAX_LIMIT][3],pre2[MAX_LIMIT][MAX],LIMIT,N,M,X,SEC_E[MAX],SEC_S[MAX],E[MAX],S[MAX];
string tmp;


int main(){
  while(cin >> LIMIT >> N >> M >> X, LIMIT|N|M|X){
    rep(i,N)cin >> tmp >> SEC_E[i] >> SEC_S[i];
    rep(i,M)cin >> tmp >> E[i] >> S[i];
    rep(i,MAX_LIMIT)rep(j,3)pre[i][j] = -1;
    rep(i,MAX_LIMIT)rep(j,MAX)pre2[i][j] = -1;
    pre[0][0] = pre2[0][0] = 0;

    rep(i,N)for(int j=1;j>=0;j--)rep(k,LIMIT+1){
	if( pre[k][j] == -1 ) continue;
	int total_money = k + SEC_E[i];
	if( total_money > LIMIT ) continue;
	pre[total_money][j+1] = max(pre[total_money][j+1],pre[k][j]+SEC_S[i]);
      }

    rep(i,3)rep(j,LIMIT+1)if( j ) pre[j][i] = max(pre[j][i],pre[j-1][i]);

    rep(i,M)for(int j=M-1;j>=0;j--)rep(k,LIMIT+1){
	if( pre2[k][j] == -1 ) continue;
	int total_money = k + E[i];
	if( total_money > LIMIT ) continue;
	pre2[total_money][j+1] = max(pre2[total_money][j+1],pre2[k][j]+S[i]);
      }

    rep(i,M+1)rep(j,LIMIT+1)if( j ) pre2[j][i] = max(pre2[j][i],pre2[j-1][i]);

    int ans = 0;

    REP(i,X,M+1)REP(j,1,3)rep(k,LIMIT+1){
      if( pre2[k][i] == -1 || pre[LIMIT-k][j] == -1 ) continue;
      int points = pre2[k][i] + pre[LIMIT-k][j];
      ans = max(ans,points);
    }

    cout << ans << endl;

  }
  return 0;
}