Timetable CodeForces - 946D （预处理+背包）

题意：n天m节课，最多可以逃k节课，每天在学校待的时间为该天上的第一节课到最后一节课持续的时间。问怎样逃课可以使这n天在学校待的时间最短，输出最短的时间。

分析：

1、预处理出每天逃j节课时在学校待的最短时间。t[i][j]

2、dp[i][j]为截止到第i天逃j节课待在学校的最短时间。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 500 + 10;

const int INF = 0x3f3f3f3f;

char pic[MAXN][MAXN];

vector<int> v[MAXN];

int t[MAXN][MAXN];

int dp[MAXN][MAXN];

int main(){

    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= n; ++i){

        scanf("%s", pic[i]);

    }

    for(int i = 1; i <= n; ++i){

        for(int j = 0; j < m; ++j){

            if(pic[i][j] == '1'){

                v[i].push_back(j);

            }

        }

    }

    for(int i = 1; i <= n; ++i){

        int len = v[i].size();

        int mi = min(len, k);

        for(int j = 0; j <= mi; ++j){//逃课数

            int rest = len - j;

            if(rest == 0){//今天不用上课

                t[i][j] = 0;

                continue;

            }

            int Mi = INF;

            for(int w = 0; w < len; ++w){

                int et = w + rest - 1;

                if(et >= len) break;

                Mi = min(Mi, v[i][et] - v[i][w] + 1);

            }

            t[i][j] = Mi;

        }

    }

    for(int i = 1; i <= n; ++i){

        for(int j = 0; j <= k; ++j){

            dp[i][j] = INF;

            for(int w = 0; w <= j; ++w){

                dp[i][j] = min(dp[i][j], dp[i - 1][w] + t[i][j - w]);

            }

        }

    }

    printf("%d\n", dp[n][k]);

    return 0;

}