链接：https://ac.nowcoder.com/acm/contest/893/H来源：牛客网
题目描述
在Casya生活的世界里，一天由m个小时组成。
最近Casya的女神终于答应在接下来的n天中与Casya聊天,Casya非常激动。
在这n天中的每一天的每一个小时中女神可能会在线或者不在线，
某个小时如果女神如果在线且Casya在线的话他们就会开心的聊一个小时；
反之如果女神在线Casya没有在线的话女神就会认为Casya放了她的鸽子而积累一点生气度。
而Casya是个很懒惰的人，他每天只愿意上线一次，当他某天下线后就不愿意再上线了。
换句话说，他每天在线的时间必须是连续的。
现在Casya已经知道每一天的每个小时女神是否会在线
Casya希望在这n天中女神的总生气度不超过k，在此前提下Casya希望他的总上线时间最小。
假设每个小时Casya和女神要么完整在线要么完整不在线，请问Casya在这n天中最小的总上线时间是多少小时？
输入描述:
第一行一个数字
T(1≤T≤30)T(1≤T≤30)--样例个数。每个样例第一行三个数字n,m,k(1≤n,m≤200,0≤k≤200)n,m,k(1≤n,m≤200,0≤k≤200)。然后这n行，每行一个长度为m的只含'0'和'1'的字符串，第i个字符串的第j个字符为'0'代表女神第i天的第j个小时不在线，为'1'表示女神第i天的第j个小时在线。保证所有样例中∑n×m∑n×m不超过5×1055×105。
输出描述:
每个样例输出一行一个数字--Casya在这n天中最小的总上线时间
示例1
输入
复制
2
2 5 1
01001
10110
2 5 0
01001
10110
输出
复制
5
8
说明
第一个样例:一种可行的方案:Casya第一天只在第2个小时上线，第五个小时女生在线而Casya不在线，生气度积累1；Casya第一天在第1、2、3、4个小时上线。Casya的总上线时间是1+4=5。第二个样例:只能老老实实上线。Casya第一天在第2、3、4、5个小时上线；Casya第一天在第1、2、3、4个小时上线。Casya的总上线时间是4+4=8。题意：给出n个01串，每个01串取一个区间，要求至少覆盖sum-k个1，其中sum为所有字符串的1的个数，并且使n个区间的总长度最短，求最短总长度题解：预处理出每个01串丢弃j个1可以得到的贡献，然后背包dp就行了
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef
long long ll;
4 #define debug(x) cout<<"["<<#x<<"]"<<" is "<<x<<endl;
5 char ch[
205][
205];
6 int dp[
205][
205],dp2[
205][
205],a[
205][
205],b[
205];
7 int main(){
8 int t;
9 cin>>
t;
10 while(t--
){
11 int n,m,k;
12 scanf(
"%d%d%d",&n,&m,&
k);
13 int sum=
0;
14 memset(dp,
0,
sizeof(dp));
15 memset(dp2,
0x3f3f3f3f,
sizeof(dp2));
16 dp2[
0][
0]=
0;
17 for(
int i=
1;i<=n;i++
){
18 scanf(
"%s",ch[i]+
1);
19 int tot=
0;
20 for(
int j=
1;j<=m;j++
){
21 if(ch[i][j]==
'1'){
22 a[i][++tot]=
j;
23 sum++
;
24 }
25 }
26 b[i]=
tot;
27 for(
int q=
0;q<=tot;q++
){
28 dp[i][tot]=a[i][tot]-a[i][
1]+
1;
29 for(
int w=
0;tot-q+w>=
1&&tot-q+w<=tot;w++
){
30 dp[i][q]=max(dp[i][q],a[i][tot]-a[i][
1]+
1-(a[i][tot-q+w]-a[i][w+
1]+
1));
31 }
32 }
33 }
34 for(
int i=
1;i<=n;i++
){
35 for(
int w=
0;w<=k;w++
){
36 for(
int j=min(b[i],w);j>=
0;j--
){
37 if(dp2[i-
1][w-j]!=
0x3f3f3f3f)dp2[i][w]=min(dp2[i][w],dp2[i-
1][w-j]+a[i][b[i]]-a[i][
1]+
1-
dp[i][j]);
38 }
39 }
40 }
41 if(sum<=k)printf(
"0\n");
42 else printf(
"%d\n",dp2[n][k]);
43 }
44 return 0;
45 }
View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/10810302.html
相关资源：各显卡算力对照表！
