BよりCの方が簡単かも。
http://arc027.contest.atcoder.jp/tasks/arc027_3
問題
初期状態としてX枚のスペシャルチケットとY枚の通常チケットを持つ。
ここでN種類のトッピングがあり、トッピングを手に入れるにはT[i]枚のチケットと交換する必要があり、うち1枚以上はスペシャルチケットでなければならない。
各トッピングの満足度H[i]が与えらえているとき、合計満足度を最大化せよ。
解法
X,Yが400と小さいので、残りチケット枚数を状態としてDPすればよい。
トッピングを手に入れる場合、スペシャルチケットは1枚だけ使うようにして、あとはできるだけ通常チケットから使っていき、足りない場合だけスペシャルチケットを使う。
O(XYN)なのでC++なら余裕で間に合う。
int X,Y,N; int T[400],H[400]; pair<double,int> P[400]; ll dp[402][402]; void solve() { int f,i,j,k,l,x,y; cin>>X>>Y>>N; FOR(i,N) cin>>T[i]>>H[i]; FOR(x,401) FOR(y,401) dp[x][y]=-1; dp[X][Y]=0; ll ret=0; FOR(i,N) { FOR(x,401) FOR(y,401) if(dp[x][y]>=0) { int dy=min(T[i]-1,y); int dx=max(1,T[i]-dy); if(y>=dy && x>=dx) { dp[x-dx][y-dy]=max(dp[x-dx][y-dy],dp[x][y]+H[i]); ret=max(ret,dp[x-dx][y-dy]); } } } cout << ret << endl; }
まとめ
オーソドックスなDP。