ちょっとの工夫で簡単になる問題。
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万円」みたいのでもいいんですよね…。