kmjp's blog

競技プログラミング参加記です

AtCoder ARC #042 : C - おやつ

ちょっとの工夫で簡単になる問題。
http://arc042.contest.atcoder.jp/tasks/arc042_c

問題

N個のおやつがある。
各おやつは値段がA[i]、満足度がB[i]である。

このうちいくつかおやつを持って遠足に行く。
「持っていくおやつのうち、どの1つのおやつを除いても合計金額がP円以内に収まる」という条件を満たすおやつの持って行き方の範囲で、合計満足度の最大値を求めよ。

解法

どれを1つ除いてもP円に収まるということは、一番安いものを除いてもP円に収まるということである。
そこで、おやつを値段の高い順で並べ替え、順にdp[おやつ番号][合計価格] := 合計満足度最大値を条件としてDPを行えばよい。

DP過程において、途中合計金額P円を超えた場合でもその合計最大値は解の候補となりうる。
ただしP円を超えるとそれ以上おやつを追加できないので、P円越えの状態に対してはそれ以上DPしてはいけない。

int N,P;
int A[5050],B[5050];
pair<int,int> PP[5050];
int ma;

int dp[15050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,N) cin>>PP[i].first>>PP[i].second;
	sort(PP,PP+N);
	
	FOR(i,N) A[N-1-i]=PP[i].first,B[N-1-i]=PP[i].second;
	dp[0]=0;
	
	FOR(i,N) {
		for(x=P;x>=0;x--) {
			ma=max(ma,dp[x]+B[i]);
			dp[x+A[i]]=max(dp[x+A[i]],dp[x]+B[i]);
		}
	}
	cout<<ma<<endl;
}

まとめ

1個の巨大な「おやつパック1万円」みたいのでもいいんですよね…。