简答题
偏难
#7505
拼题A打卡奖励 拼题 A 的教超搞打卡活动,指定了 N 张打卡卷,第 i 张打卡卷需要 mi 分钟做完,完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多…
拼题A打卡奖励
拼题 A 的教超搞打卡活动,指定了 N 张打卡卷,第 i 张打卡卷需要 mi 分钟做完,完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多只能做一次。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币?
时间限制:7000
内存限制:524288
输入
输入首先在第一行中给出两个正整数 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
提示
样例解释: 选择最后两张卷子,可以在 50+60=110 分钟内获得 18+22=40 枚金币。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++
#include <iostream>
using namespace std;
const int N = 1e3 + 10, M = 365 * 24 * 60 + 10;
int n, m;
int v[N], w[N];
int dp[M];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
cin >> n >> m;
cin >> v[0];
int yuanzi = v[0];
for (int i = 1; i < n; i ++ ) {
cin >> v[i];
yuanzi = gcd(v[i], yuanzi);
}
for (int i = 0; i < n; i ++ ) cin >> w[i];
for (int i = 0; i < n; i ++ ) {
int cnt = 0;
for (int j = m; j >= v[i]; j -= yuanzi ) {
if (dp[j - v[i]] + w[i] > dp[j]) dp[j] = dp[j - v[i]] + w[i];
else cnt ++;
if (cnt == 10) break;
}
}
cout << dp[m] << endl;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言
#include <stdio.h>
#define N 1004
#define INF 0x3f3f3f3f
int n, m;
int w[N], v[N];
int dp[30005];
int mv = 0;
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &w[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &v[i]);
mv += v[i];
}
for (int j = 0; j <= mv; ++j) {
dp[j] = INF;
}
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = mv; j >= 0; --j) {
if (j >= v[i]) {
dp[j] = min(dp[j - v[i]] + w[i], dp[j]);
} else {
dp[j] = dp[j];
}
}
}
for (int j = mv; j >= 0; j--) {
if (dp[j] <= m) {
printf("%d", j);
break;
}
}
return 0;
}</pre>
这道题暂未补解析。