2019年湘潭大学程序设计竞赛（重现赛）H题前缀和+分组背包

链接&＃xff1a;https://ac.nowcoder.com/acm/contest/893/H
来源&＃xff1a;牛客网
 

Chat

时间限制&＃xff1a;C/C&＃43;&＃43; 1秒&＃xff0c;其他语言2秒
空间限制&＃xff1a;C/C&＃43;&＃43; 32768K&＃xff0c;其他语言65536K
64bit IO Format: %lld

题目描述

在Casya生活的世界里&＃xff0c;一天由m个小时组成。
最近Casya的女神终于答应在接下来的n天中与Casya聊天,Casya非常激动。

在这n天中的每一天的每一个小时中女神可能会在线或者不在线&＃xff0c;
某个小时如果女神如果在线且Casya在线的话他们就会开心的聊一个小时&＃xff1b;
反之如果女神在线Casya没有在线的话女神就会认为Casya放了她的鸽子而积累一点生气度。

而Casya是个很懒惰的人&＃xff0c;他每天只愿意上线一次&＃xff0c;当他某天下线后就不愿意再上线了。
换句话说&＃xff0c;他每天在线的时间必须是连续的。

现在Casya已经知道每一天的每个小时女神是否会在线

Casya希望在这n天中女神的总生气度不超过k&＃xff0c;在此前提下Casya希望他的总上线时间最小。
假设每个小时Casya和女神要么完整在线要么完整不在线&＃xff0c;请问Casya在这n天中最小的总上线时间是多少小时&＃xff1f;

输入描述:

第一行一个数字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行&＃xff0c;每行一个长度为m的只含&＃39;0&＃39;和&＃39;1&＃39;的字符串&＃xff0c;
第i个字符串的第j个字符为&＃39;0&＃39;代表女神第i天的第j个小时不在线&＃xff0c;为&＃39;1&＃39;表示女神第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个小时上线&＃xff0c;第五个小时女生在线而Casya不在线&＃xff0c;生气度积累1&＃xff1b;
Casya第一天在第1、2、3、4个小时上线。
Casya的总上线时间是1&＃43;4&＃61;5。
第二个样例:
只能老老实实上线。
Casya第一天在第2、3、4、5个小时上线&＃xff1b;
Casya第一天在第1、2、3、4个小时上线。
Casya的总上线时间是4&＃43;4&＃61;8。
思路&＃xff1a;

先用前缀和把每一天女神可以增加的0到sum[n]需要花费的最少时间算出来
 fij 是第i天&＃xff0c;女神生气度为j最小需要花费的小时

就可以转换成一个分组背包&＃xff0c;n天的时间&＃xff0c;每天有0到sum[n]个物品&＃xff0c;然后每组物品价值是需要花费的最小时间&＃xff0c;每组的体积就是女神的生气度

int n,t,m,kk;
int a[300][300];
int f[300][300];
int dp[300][300];
int sum[300][300];
int main()
{ios::sync_with_stdio(false);int t; cin >> t;while(t--){cin >> n >> m >> kk;MS0(sum);for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){for(int j &＃61; 0;j <&＃61; m;j&＃43;&＃43;){f[i][j] &＃61; 1e9;dp[i][j] &＃61; 1e9;}}for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){string str;cin >> str;for(int j &＃61; 0;j // cout <// cout <// for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){
// for(int j &＃61; 0;j <&＃61; m;j&＃43;&＃43;){
// cout <// }
// cout <// }for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){f[i][sum[i][m]] &＃61; 0;for(int j &＃61; 0;j <&＃61; kk;j&＃43;&＃43;){dp[i][j] &＃61; 1e9;for(int k &＃61; 0;k <&＃61; min(m,j);k&＃43;&＃43;){dp[i][j] &＃61; min(dp[i - 1][j - k] &＃43; f[i][k],dp[i][j]);}}}int ans &＃61; 2e9;for(int i &＃61; 0;i <&＃61; kk;i&＃43;&＃43;){ans &＃61; min(ans,dp[n][i]);}cout <}