yukicoder : No.1715 Dinner 2

★3が多いとどれから解くか迷うよね。
https://yukicoder.me/problems/no/1715

問題

N個の料理があり、それぞれ食べるとまず元気がP[i]減少後、Q[i]増加する。

N個の料理を、D個順に食べる。
その際、同じ料理を複数回食べてもよいが、同じ料理を連続して食べることは許可されない。
元気の最小値を最大化せよ。

解法

解vに二分探索することを考える。
すなわち、元気がv未満にならないようD個料理を選べるかを考えよう。

f(n,i) := n個料理を選んだ時、最後にi番目の料理を選んだ場合の元気の最大値
としてf(n,i)＜vとなる状態を経ずにf(D,*)をv以上にできるか判定しよう。
二分探索の中の処理はO(ND)で解ける。

int N,D;
int P[1010],Q[1010];

int ok(ll v) {
	int dp[1010];
	int i,j;
	FOR(i,N+1) dp[i]=-1<<30;
	FOR(i,D) {
		vector<pair<int,int>> C;
		if(i==0) {
			C.push_back({0,N});
		}
		else {
			C.push_back({1<<30,N});
		}
		FOR(j,N) if(dp[j]>=-1<<29) {
			C.push_back({-dp[j],j});
		}
		sort(ALL(C));
		FOR(j,N) {
			int tar=(C[0].second==j);
			if(-C[tar].first-P[j]<v) {
				dp[j]=-1<<30;
			}
			else {
				dp[j]=-C[tar].first-P[j]+Q[j];
			}
		}
		
	}
	FOR(i,N) if(dp[i]>=v) return 1;
	return 0;
}

まとめ

まだ1問目は簡単。