本文主要是介绍Educational Codeforces Round 39 (Rated for Div. 2) D - Timetable背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/946/problem/D
题意：
有n天时间，每天有m个时间段，0代表不上课，1代表上课，一天呆在学校里的时间是第一节课到最后一节课的时间，你可以逃k节课，求呆在学校的最短时间。
题解：
我们可以设一个dp[i][j]代表前i天逃了j次课最多不在学校的时间。
先用前缀和求出上课的数量，方便等会计算。用一个val数组表示逃了多少节课不在学校的最长时间，因为数据范围只有500，所以可以直接暴力出来。
#include<bits/stdc++.h>
using namespace std;
const int N=505;
char Map[N][N];
int sum[N][N],val[N][N],dp[N][N];
int main()
{int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%s",Map[i]+1);for(int j=1;j<=m;j++)sum[i][j]=sum[i][j-1]+Map[i][j]-'0';//课程的前缀和}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int t=j-1;t<=m;t++)//t=j-1表示不逃{int num=sum[i][t]-sum[i][j-1];//表示几门课没逃val[i][sum[i][m]-num]=max(val[i][sum[i][m]-num],m-(t-j+1));//val表示逃了几门课不在学校的最多时间//因为这个是遍历一遍过来，所有情况都考虑到了，那么就取最大值}}}for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){for(int t=0;t<=j;t++)dp[i][j]=max(dp[i][j],dp[i-1][j-t]+val[i][t]);}}int ans=0;for(int i=0;i<=k;i++)ans=max(ans,dp[n][i]);printf("%d\n",n*m-ans);return 0;
}这篇关于Educational Codeforces Round 39 (Rated for Div. 2) D - Timetable背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
