php+做网站,素材下载,网站建设论文ppt,48快装旧房翻新公司电话拼题 A 的教超搞打卡活动#xff0c;指定了 N 张打卡卷#xff0c;第 i 张打卡卷需要 mi 分钟做完#xff0c;完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多只能做一次#xff0c;并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币指定了 N 张打卡卷第 i 张打卡卷需要 mi 分钟做完完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多只能做一次并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币
输入格式
输入首先在第一行中给出两个正整数 N≤103 和 M≤365×24×60分别对应打卡卷的数量和以“分钟”为单位的活动总时长不超过一年。随后一行给出 N 张打卡卷要花费的时间 mi≤600最后一行给出 N 张打卡卷对应的奖励金币数量 ci≤30。上述均为正整数一行内的数字以空格分隔。
输出格式
在一行中输出最多可以赢得的金币数量。
输入样例
5 110
70 10 20 50 60
28 1 6 18 22
输出样例
40
样例解释
选择最后两张卷子可以在 5060110 分钟内获得 182240 枚金币。
做法
01背包问题。
dp数组第一维是考虑了前i个卷子第二维是花费的时间。
#includebits/stdc.h
using namespace std;
int n,m;
int ans-0x3f3f3f3f;
int a[1010],b[1010];
int dp[1010][600000];
int main(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) scanf(%d,b[i]);memset(dp,-0x3f,sizeof(dp));dp[0][0]0;for(int i1;in;i){//考虑前i个 for(int j0;jm;j){if(ja[i]) dp[i][j]max(dp[i][j],dp[i-1][j-a[i]]b[i]);dp[i][j]max(dp[i][j],dp[i-1][j]);//别忘了更新当前的 }}for(int i0;im;i) ansmax(ans,dp[n][i]);coutans;
}
但是吧dp数组超空间了得改成1维数组。
#includebits/stdc.h
using namespace std;
int n,m;
int ans-0x3f3f3f3f;
int a[1010],b[1010];
int dp[600000];
int main(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) scanf(%d,b[i]);memset(dp,-0x3f,sizeof(dp));dp[0]0;for(int i1;in;i){for(int jm;j0;j--){//倒序 if(ja[i]) dp[j]max(dp[j],dp[j-a[i]]b[i]);}}for(int i0;im;i) ansmax(ans,dp[i]);coutans;
}
这么交上去结果运行超时了有几个的过不去。为什么呢因为我们的m太大了。那我们就把dp数组的下标表示为金币而不是时间。注意dp数组初始化的值
#includebits/stdc.h
using namespace std;
int n,m;
int a[1010],b[1010];
int dp[30010];
int mv;
int main(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) scanf(%d,b[i]),mvb[i];memset(dp,0x3f,sizeof(dp));//初始化的值不同dp[0]0;for(int i1;in;i){for(int jmv;j0;j--){if(jb[i]) dp[j]min(dp[j],dp[j-b[i]]a[i]);//取最小值因为取得相同金币时间越少越好}}for(int jmv;j0;j--){if(dp[j]m){coutj;return 0;}}
}
