友達以上恋人以下 [いろはちゃんコンテスト Day1 G]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_g

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/iroha2019-day1/submissions/5195581

DPで解く。
dp[i][m] := i日目に好意をほのめかし、今までm回好意をほのめかしているときの、機嫌の最大値
K日以上時間は開けないので、遷移元のdp[j][m-1]はi-j≦Kを満たす必要がある。
これを満たすように遷移を書いて更新していく。
DP配列はちゃんと初期化することぐらい。
dp[N-K+1][M]～dp[N][M]の最大値が答え。
条件を満たすように行動できない場合は負が答えになっているはずなので、-1に整形して答え。

int N, M, K, A[1010];
ll dp[370][370];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> K;
	rep(i, 1, N + 1) cin >> A[i];
 
	rep(i, 0, N + 1) rep(m, 0, M + 1) dp[i][m] = -infl;
	dp[0][0] = 0;
 
	rep(i, 1, N + 1) rep(m, 1, M + 1) {
		rep(j, 0, i) if (i - j <= K) {
			chmax(dp[i][m], dp[j][m - 1] + A[i]);
		}
	}
 
	ll ans = -infl;
	rep(i, N - K + 1, N + 1) chmax(ans, dp[i][M]);
 
	if (ans < 0) ans = -1;
 
	cout << ans << endl;
}