yukicoder : No.951 【本日限定】１枚頼むともう１枚無料！

最初悩んだけど気が付いてしまえば簡単だった。
https://yukicoder.me/problems/no/951

問題

N通りのピザが1枚ずつある。
それぞれの値段とおいしさが与えられる。
ピザを1枚買うと、それ以下の値段のピザのうち購入金額以下の物を1枚もらえる。

K円で得られるおいしさの総和の最大値を求めよ。

解法

ピザを金額降順に並べたとする。
先に手に入れるピザの集合を決めたとき、できるだけ高いピザをもらうようにするのがお得である。
よって、手に入れるピザのうち奇数枚目は購入し、偶数枚目はもらうことになる。
そこで、「次に手に入れるピザは買うかもらうか」というフラグを導入すると簡単なDPになる。

f(n,k,b) := n枚目までのピザについて入手を決めたとき、残金がkで、次に入手するもらえるかどうかの真偽値がbの時、そこまでに得られるおいしさの総和の最大値

として端から埋めていこう。

int N,K;
pair<int,int> P[5050];
int dp[5151][5151][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
	}
	sort(P,P+N);
	reverse(P,P+N);
	FOR(x,5050) FOR(y,5050) dp[x][y][0]=dp[x][y][1]=-1<<30;
	dp[0][K][0]=0;
	
	FOR(i,N) {
		FOR(j,K+1) {
			// no
			dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]);
			dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]);
			// buy
			if(j>=P[i].first) dp[i+1][j-P[i].first][1]=max({dp[i+1][j-P[i].first][1],dp[i][j][0]+P[i].second,dp[i][j][1]+P[i].second});
			// free
			dp[i+1][j][0]=max({dp[i+1][j][0],dp[i][j][1]+P[i].second});
		}
	}
	
	int ma=0;
	FOR(i,K+1) ma=max({ma,dp[N][i][0],dp[N][i][1]});
	cout<<ma<<endl;
	
	
	
}

まとめ

ピザ屋の配達を頼んだことないなぁ…。