RUPC E, AOJ-2285: アニペロ (Anipero)

その他のコンテスト AOJ

問題概要

A[i] = (e[i], s[i]), B[i] = (ee[i], ss[i])が与えられる(N<100)。AのうちからX以上選んで、Bのうちから1or2個選んでΣee[i] + Σe[i]をLIMIT(<1000)以下になるようにしてΣss[i] + Σs[i]を最大化する問題。

考えたこと

  • DP臭がする。あとこれ入力で名前読み取る意味ないよね…。
  • シークレットとスタンダード(概要中のA, B)を別個に考えてよい気がする。
  • それぞれ、費用いくらのときの最大の満足度を覚えておけば最後にO(LIMIT^2)で全ての組み合わせを計算するだけでよい。
  • これで部分問題に落とせた。
  • DPで必要な状態は、(何人目、何人既に選んだ、使ったお金)で状態数O(M^2*LIMIT)。遷移は選ぶか選ばないかの2通り。なのでこれで行けそう。
  • サクッと書く。MLE！
  • 言われてみれば。まあこれはすぐに配列再利用すればいいことに気づく。メモ化で書いてなくてよかった。
    • とはいえ10^7*4は40MBでSRMなら通るレベル。この問題は32MBなので落ちた。
    • 答えの上限が小さいので、実はshort型にするだけでもよかった。
  • 修正。無事AC。

本番で通ったコード

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_LIMIT = 1000;
const int MAX_N = 100;
const int MAX_X = 100;
const int INF = 1<<29;

int SEC_ANS[MAX_LIMIT + 1];
int STD_ANS[MAX_LIMIT + 1];

int dp[2][MAX_N+1][MAX_LIMIT+1]; //(何人目、何人選んだ、使ったお金)

int LIMIT, X;
int E[MAX_N];
int S[MAX_N];

void sub_solve(const int N, int lb, int ub, int ans[MAX_LIMIT + 1]){

	//初期化
	for(int i=0; i<2; i++){
		for(int j=0; j<=MAX_N; j++){
			fill(dp[i][j], dp[i][j] + (MAX_LIMIT+1), -INF);
		}
	}

	//基底
	dp[0][0][0] = 0;

	//DP
	for(int i=0; i<N; i++){
		int cur = (i&1), next = 1 - cur;

		for(int j=0; j<=MAX_N; j++){
			fill(dp[next][j], dp[next][j] + (MAX_LIMIT+1), -INF);
		}

		for(int j=0; j<=ub; j++){
			for(int k=0; k<=LIMIT; k++)if(dp[cur][j][k] >= 0){
				//i人目を採用
				if(j < ub){
					int next_cost = k + E[i];
					if(next_cost <= LIMIT){
						dp[next][j+1][next_cost] = max(dp[next][j+1][next_cost] , dp[cur][j][k] + S[i]);
					}
				}

				//i人目を不採用
				dp[next][j][k] = max(dp[next][j][k], dp[cur][j][k]);
			}
		}
	}

	//後処理
	fill(ans, ans+(LIMIT+1), -INF);

	for(int l = lb; l<=ub; l++){
		for(int i=0; i<=LIMIT; i++){
			ans[i] = max(ans[i], dp[(N&1)][l][i]);
		}
	}
}

int solve(){
	int ans = 0;
	for(int i=0; i<=LIMIT; i++){
		for(int j=0; j<=LIMIT; j++)if(i + j <= LIMIT){
			ans = max(ans, SEC_ANS[i] + STD_ANS[j]);
		}
	}

	return ans;
}

int main(){
	int N, M;
	while(scanf("%d%d%d%d",&LIMIT, &N, &M, &X), LIMIT){
		//シークレット
		for(int i=0; i<N; i++){
			cin.ignore();
			string trash;
			cin >> trash >> E[i] >> S[i];
		}
		sub_solve(N, 1, 2, SEC_ANS);

		//スタンダード
		for(int i=0; i<M; i++){
			cin.ignore();
			string trash;
			cin >> trash >> E[i] >> S[i];
		}
		sub_solve(M, X, M, STD_ANS);


		printf("%d\n", solve());
	}

	return 0;
}