0-1背包-变形

题目链接:https://ac.nowcoder.com/acm/contest/642/D
题目大意:


思路:一开始想的是,01背包dp出dp[n][s-1]。然后标记选的音乐,从没有标记的音乐找到MAX,输出:dp[n][s-1]+MAX;
然后WA了,
想到一个错误样例:

1
5 7
6 1 1 1 3

方案是:6
那么答案是: 6+3=9

实际上:
可以:选择1 1 1 3=6
答案:6+6=12

正确的思路:从输入的时候找到最大值,跑01背包dp[n][s],dp时不能包含MAX的音乐,如果dp[n][s]等于s说明必须要去一首音乐,并且可以加上其他的音乐,那么就可以:dp[n][s-1]+MAX;这样就可以得到最大值。

如果dp[n][s]!=s,那么说明有时间来播放最长时间的音乐,输出dp[n][s]+MAX;

#include<bits/stdc++.h>
using namespace std;

int a[210];
int b[210];
int dp[80005];//背包的容量

int main()
{
    int T, n, s;
    scanf("%d",&T);
    while(T--)
    {
        int MAX=0, k=-1;
        scanf("%d%d",&n,&s);
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
            if(MAX<b[i])
            {
                MAX=b[i];
                k=i;
            }
        }


        for(int i=1;i<=n;i++)
        {
            if(i==k)
            {
                continue;
            }
            for(int j=s; j>=a[i]; j--)
            {
                dp[j]=max(dp[j], dp[j-a[i]]+b[i]);
            }
        }
        if(dp[s]==s)
        {
            printf("%d\n",dp[s-1]+MAX);
        }
        else
        {
            printf("%d\n",dp[s]+MAX);
        }
    }

    return 0;
}

全部评论

相关推荐

Aaso:挺好的,早挂早超生
点赞 评论 收藏
分享
01-23 14:54
同济大学 Java
热爱敲代码的程序媛:给你提几点【专业技能】这个模块里面可优化的地方:1.【具备JVM调优经验】可以去b站上搜一下JVM调优的视频,估计一两个小时凭你的学习能力就能掌握JVM调优的实践方面的技能。2.【MySql优化】MySql这一栏,你去b站或者找个博客看看MySql优化,学一下,如果你本身比较熟悉MySql语句的话,那基本半天时间凭你的学习能力MySql语句优化方面的技能你也能掌握个差不多。以上1,2两点主要是因为我看你专业技能大部分都说的是偏理论,没有写应用。再就是最后,你结合你的项目,想一想你的项目中哪些sql语句是可以用MySql优化的,到时候你面试的时候也好结合着说一下。
点赞 评论 收藏
分享
03-14 11:58
门头沟学院 Java
腾讯暑期实习java选手,完全不懂C++,貌似游戏行业都是用C++的而且天美好像在成都,个人比较想去上海或深圳
siestaaaaaa:天美不止在成都,深圳上海都有。 游戏服务器也不全是cpp,至少我们项目是java ,但是工作中什么语言都会用到,比如cpp、lua、py等等,语言本身其实不重要
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务