当前位置:   article > 正文

2021 RoboCom 世界机器人开发者大赛-本科组(复赛):拼题A打卡奖励_robocom2021复赛

robocom2021复赛

拼题 A 的教超搞打卡活动,指定了 N 张打卡卷,第 i 张打卡卷需要 mi​ 分钟做完,完成后可获得 ci​ 枚奖励的金币。活动规定每张打卡卷最多只能做一次,并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币?

输入格式:

输入首先在第一行中给出两个正整数 N(≤103) 和 M(≤365×24×60),分别对应打卡卷的数量和以“分钟”为单位的活动总时长(不超过一年)。随后一行给出 N 张打卡卷要花费的时间 mi​(≤600),最后一行给出 N 张打卡卷对应的奖励金币数量 ci​(≤30)。上述均为正整数,一行内的数字以空格分隔。

输出格式:

在一行中输出最多可以赢得的金币数量。

输入样例:

  1. 5 110
  2. 70 10 20 50 60
  3. 28 1 6 18 22

输出样例:

  1. 40

样例解释:

选择最后两张卷子,可以在 50+60=110 分钟内获得 18+22=40 枚金币。

做法

01背包问题

dp数组第一维是考虑了前i个卷子,第二维是花费的时间。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int ans=-0x3f3f3f3f;
  5. int a[1010],b[1010];
  6. int dp[1010][600000];
  7. int main(){
  8. scanf("%d%d",&n,&m);
  9. for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  10. for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  11. memset(dp,-0x3f,sizeof(dp));
  12. dp[0][0]=0;
  13. for(int i=1;i<=n;i++){//考虑前i个
  14. for(int j=0;j<=m;j++){
  15. if(j>=a[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+b[i]);
  16. dp[i][j]=max(dp[i][j],dp[i-1][j]);//别忘了更新当前的
  17. }
  18. }
  19. for(int i=0;i<=m;i++) ans=max(ans,dp[n][i]);
  20. cout<<ans;
  21. }

但是吧,dp数组超空间了,得改成1维数组。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int ans=-0x3f3f3f3f;
  5. int a[1010],b[1010];
  6. int dp[600000];
  7. int main(){
  8. scanf("%d%d",&n,&m);
  9. for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  10. for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  11. memset(dp,-0x3f,sizeof(dp));
  12. dp[0]=0;
  13. for(int i=1;i<=n;i++){
  14. for(int j=m;j>=0;j--){//倒序
  15. if(j>=a[i]) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
  16. }
  17. }
  18. for(int i=0;i<=m;i++) ans=max(ans,dp[i]);
  19. cout<<ans;
  20. }

这么交上去结果运行超时了,有几个的过不去。为什么呢,因为我们的m太大了。那我们就把dp数组的下标表示为金币,而不是时间。注意dp数组初始化的值

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int a[1010],b[1010];
  5. int dp[30010];
  6. int mv;
  7. int main(){
  8. scanf("%d%d",&n,&m);
  9. for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  10. for(int i=1;i<=n;i++) scanf("%d",&b[i]),mv+=b[i];
  11. memset(dp,0x3f,sizeof(dp));//初始化的值不同
  12. dp[0]=0;
  13. for(int i=1;i<=n;i++){
  14. for(int j=mv;j>=0;j--){
  15. if(j>=b[i]) dp[j]=min(dp[j],dp[j-b[i]]+a[i]);//取最小值,因为取得相同金币,时间越少越好
  16. }
  17. }
  18. for(int j=mv;j>=0;j--){
  19. if(dp[j]<=m){
  20. cout<<j;
  21. return 0;
  22. }
  23. }
  24. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/900943
推荐阅读
相关标签
  

闽ICP备14008679号