Heaters [Codeforces Round #515 (Div. 3) B]

http://codeforces.com/contest/1066/problem/B

N個のヒーターがあり、位置posにあるヒーターは[pos-R+1, pos+R-1]を温めることができる。
N個のヒーターのうち、一部しか電源がついていない。
ここからいくつかのヒーターを消して、全ての位置が暖められるようにする。
最小で何個のヒーターを残せるか。
もともと全ての位置を暖められないなら、-1を答える。

解法

http://codeforces.com/contest/1066/submission/44193670

DPをする
DP[i][j] := i番目のヒーターまで見終わっていて、j番目のヒーターまで暖められているときのついているヒーターの最小数
遷移が割と難しい。
ヒーターを使うと二番目の添字が更新される感じ。
ヒーターで暖められていない部分がないかをチェックしながら更新していく。

int N, R, A[1010];
int dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> R;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N + 1) rep(j, 0, N + 1) dp[i][j] = inf;

    dp[0][0] = 0;
    rep(i, 0, N) rep(j, 0, N + 1) {
        chmin(dp[i + 1][j], dp[i][j]);
        if (A[i] and i - R + 1 <= j) chmin(dp[i + 1][max(j, min(N, i + R))], dp[i][j] + 1);
    }
    
    if (dp[N][N] == inf) dp[N][N] = -1;
    cout << dp[N][N] << endl;
}