はまやんはまやんはまやん

hamayanhamayan's blog

Timetable [Educational Codeforces Round 39 D]

http://codeforces.com/contest/946/problem/D

M分の長さの日がN日間ある。
i日のj分に授業があればS[i][j] = 1である。
ある日に学校に行くべき時間は最初の授業の時間から最後の授業の時間である。
ここで、K回授業をサボれる時に、学校に行く時間の最小時間は?

前提知識

解法

http://codeforces.com/contest/946/submission/36153659

3つの配列を作ろう。
ones[day][i] := day日目において、i分までにある授業の数
cost[day][skip] := day日目において、skip回授業をサボったときの学校に行く最小時間
dp[day][skip] := day日目まででskip回授業をサボったときに学校に行った時間の累計最小時間
onesは累積和で作ればいい。
costはskipの全探索ではなく、[l,r]の全探索で構築する。
dpはskipを差分dsの全探索で構築していく。

int N, M, K;
string S[505];
int dp[505][505], cost[505][505], ones[505][505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) cin >> S[i];

    // make ones
    rep(day, 0, N) {
        rep(i, 0, M) if(S[day][i] == '1') ones[day][i] = 1;
        rep(i, 1, M) ones[day][i] += ones[day][i - 1];
    }

    // make cost
    rep(day, 0, N) rep(skip, 0, K + 1) cost[day][skip] = inf;

    rep(day, 0, N) {
        cost[day][ones[day][M - 1]] = 0;

        rep(l, 0, M) rep(r, l, M) if(S[day][l] == '1' and S[day][r] == '1') {
            int rht = ones[day][M - 1];
            rht -= ones[day][r];

            int lft = 0;
            if (l) lft = ones[day][l - 1];

            chmin(cost[day][rht + lft], r - l + 1);
        }
    }

    // make dp
    rep(day, 0, N + 1) rep(skip, 0, K + 1) dp[day][skip] = inf;
    dp[0][0] = 0;

    rep(day, 0, N) rep(skip, 0, K + 1) rep(ds, 0, K + 1) if (skip + ds <= K) {
        chmin(dp[day + 1][skip + ds], dp[day][skip] + cost[day][ds]);
    }

    int ans = inf;
    rep(skip, 0, K + 1) chmin(ans, dp[N][skip]);
    cout << ans << endl;
}