chat(简单背包)
链接：https://ac.nowcoder.com/acm/contest/893/H
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
在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。
解析:
将该题转化为背包来做,
产生至多k点生气值,求最小消耗的小时数目
计算每组产生i点生气值的最大小时数
直接暴力循环计算和女神一起玩i小时需要的时间,反转一下就是产生的生气值的时间
然后直接简单dp计算p以内生气值消耗的小时,遍历取最小值,总复杂度O(N*M*M+N*M*P)
ac:
#include
#define inf 0x3f3f3f3f
#define MAXN 205
using namespace std;
char str[MAXN];
int cc[MAXN];
int dd[MAXN][MAXN];//dd[i][j],i组价值j的需要的体积
int ee[MAXN][MAXN];//丢掉int vc[MAXN];//记录容量
int dp[MAXN][MAXN];//背包int main()
{int t,n,m,p;scanf("%d",&t);while(t--){memset(cc,0,sizeof(cc));memset(vc,0,sizeof(vc));memset(dp,inf,sizeof(dp));memset(dd,inf,sizeof(dd));scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++)dd[i][0]=0;for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++){cc[j]=cc[j-1];if(str[j]=='1')cc[j]++;}for(int j=1;j<=m;j++)for(int k=1;k<=m;k++)if(cc[k]>cc[j-1])dd[i][cc[k]-cc[j-1]]=min(dd[i][cc[k]-cc[j-1]],k-j+1);for(int j=1;j<=m;j++){if(dd[i][j]!=inf)vc[i]++;else{break;}}for(int j=0;j<=vc[i];j++)ee[i][j]=dd[i][vc[i]-j];}dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=p;j++){for(int k=0;k<=min(vc[i],j);k++){dp[i][j]=min(dp[i][j],dp[i-1][j-k]+ee[i][k]);}}}int ans=1e9;for(int i=0;i<=p;i++)ans=min(ans,dp[n][i]);printf("%d\n",ans);}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！