首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;iostream&gt;   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 &gt;&gt; n &gt;&gt; m;     cin &gt;&gt; v[0];     int yuanzi = v[0];     for (int i = 1; i &lt; n; i ++ ) {         cin &gt;&gt; v[i];         yuanzi = gcd(v[i], yuanzi);     }     for (int i = 0; i &lt; n; i ++ ) cin &gt;&gt; w[i];     for (int i = 0; i &lt; n; i ++ ) {         int cnt = 0;         for (int j = m; j &gt;= v[i]; j -= yuanzi ) {             if (dp[j - v[i]] + w[i] &gt; dp[j]) dp[j] = dp[j - v[i]] + w[i];             else cnt ++;             if (cnt == 10) break;         }     }     cout &lt;&lt; dp[m] &lt;&lt; endl; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #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 &lt; b ? a : b; } int main() {     scanf("%d %d", &amp;n, &amp;m);          for (int i = 1; i &lt;= n; ++i) {         scanf("%d", &amp;w[i]);     }          for (int i = 1; i &lt;= n; ++i) {         scanf("%d", &amp;v[i]);         mv += v[i];     }     for (int j = 0; j &lt;= mv; ++j) {         dp[j] = INF;     }     dp[0] = 0;     for (int i = 1; i &lt;= n; ++i) {         for (int j = mv; j &gt;= 0; --j) {             if (j &gt;= v[i]) {                 dp[j] = min(dp[j - v[i]] + w[i], dp[j]);             } else {                 dp[j] = dp[j];             }         }     }     for (int j = mv; j &gt;= 0; j--) {         if (dp[j] &lt;= m) {             printf("%d", j);             break;         }     }     return 0; }</pre>
这道题暂未补解析。