牛客练习赛75 B 小D和他的魔法石

广义肥波

https://ac.nowcoder.com/acm/contest/10507/A

牛客练习赛75 B 小D和他的魔法石
题目连接:https://ac.nowcoder.com/acm/contest/10507/B

启用贪心的想法用完k次机会,再使用完全背包即可
贪心思路就是大的魔力配合上小的抗力,因为1e3的数据量,所以n2的做法也可以
对每一棵魔法树的魔力进行从大到小的排序,往后找最小的抗力来对这棵树的抗力进行交换,
结束上述过程后如果机会k还有剩余,那么对k的情况进行判断
如果k是偶数,那么直接忽略,因为俩颗树交换俩次等于不变

如果是奇数,那么交换魔力最低的俩棵树的抗力
#include<bits/stdc++.h>
using namespace std;


const int MAXN=1e3+10;
typedef long long ll;
#define INF 0x3f3f3f3f
ll dp[MAXN];

struct node{
    ll ai,bi;
    friend bool operator <(node a,node b){
        return a.bi>b.bi;
    }
}a[MAXN];

int main()
{
    int n,m,k,i,j;
    scanf("%d %d %d",&n,&m,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i].ai);
    }
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i].bi);
    }
    sort(a+1,a+n+1);
    i=1;
    while(k>0){
        ll minm=INF,ind=0;
        for(j=i+1;j<=n;j++){
            if(a[j].ai<minm){
                minm=a[j].ai;
                ind=j;
            }
        }
        if(minm<a[i].ai){
            a[ind].ai=a[i].ai;
            a[i].ai=minm;
            k--;
        }
        i++;
        if(i>n) break;
    }
    if(k%2){
        ll temp=a[n-1].ai;
        a[n-1].ai=a[n].ai;
        a[n].ai=temp;
    }
    for(i=1;i<=n;i++){
        for(j=a[i].ai;j<=m;j++){
            dp[j]=max(dp[j],dp[j-a[i].ai]+a[i].bi);
        }
    }
    printf("%lld\n",dp[m]);
    return 0;
}

全部评论

相关推荐

码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:10
直接上图
牛客13578115...:改得一般,不值80
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务