kmjp's blog

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

AtCoder ARC #027 : C - 最高のトッピングにしような

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。