Dinner time [yukicoder No.818] - はまやんはまやんはまやん

前提知識

動的計画法

解説

A[i],B[i]や産ませる鶏肉にするという部分が少しむずかしいのでなんとかする。
あるニワトリiについてj回操作を行えるとすると、美味しさの総和の最大値は

A[i] * j
A[i] * (j - 1) + B[i]
B[i]

のいずれかになる。これは、
A[i] * (j - 1) + B[i]　＜　A[i] * (j-2) + B[i]
であるなら、どんどんj-2部分を小さくしていき、結果B[i]が最大になるためである。
これを関数にしておこう。
get(i,j) := ニワトリiについてj回操作を行ったときのそのニワトリから得られる美味しさの総和の最大値
実際の中身は、今後の実装に合わせてあるので、中身はまだちゃんと見なくていい。
　
これで、難しいシステムが減った。
あるニワトリへの操作回数について考えると、1番からニワトリを見ていくと、広義単調減少になっている必要がある。
ニワトリへの操作はそれ以外は独立に行えるので、これでDPができそうだ。
　
DP[i][j] := i番目までのニワトリで最後のニワトリをj回操作するときの美味しさの総和の最大値
これはO(NM)となるので厳しい。
　
唐突だが、あるニワトリについて操作する回数は0回、1回、M回の3択になる。
貪欲方針をDPに加えて、遷移と状態を削減する。
これは一応DPの典型テクではある。
ここの【テク17】（【テク3】もかも）
DP[i][0] := i番目までのニワトリで最後のニワトリを0回操作するときの美味しさの総和の最大値
DP[i][1] := i番目までのニワトリで最後のニワトリを1回操作するときの美味しさの総和の最大値
DP[i][2] := i番目までのニワトリで最後のニワトリをM回操作するときの美味しさの総和の最大値
というふうにする。
これに合わせてget関数の引数jも0,1,2なら0,1,Mとして計算する。
　
他にも2つ注意点があるので、これをクリアするとAC。

1. 最初のニワトリは必ずM回使われる
2. 答えは負になる可能性もあるので、初期値は-∞としておく

int N, M, A[101010], B[101010];
ll dp[101010][3];
//---------------------------------------------------------------------------------------------------
ll get(int i, int j) {
	if (j == 0) return 0;
	else if (j == 1) return max(A[i], B[i]);
	else {
		if (M == 1) return max(A[i], B[i]);
		else return max({ 1LL * A[i] * M, 1LL * A[i] * (M - 1) + B[i], 1LL * B[i] });
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, N) cin >> A[i] >> B[i];

	rep(i, 0, N + 1) rep(j, 0, 3) dp[i][j] = -infl;
	chmax(dp[1][2], get(0, 2));

	rep(i, 1, N) rep(j, 0, 3) if (-infl <= dp[i][j]) rep(j2, 0, 3) if (j2 <= j) {
		chmax(dp[i + 1][j2], dp[i][j] + get(i, j2));
	}

	ll ans = -infl;
	rep(j, 0, 3) chmax(ans, dp[N][j]);
	cout << ans << endl;
}