首页 > 其他分享 >每日一题 背包,dp,兵营力量训练

每日一题 背包,dp,兵营力量训练

时间:2024-09-04 09:20:48浏览次数:9  
标签:背包 int 精力 兵营 界线 力量 分配 dp

首先,读完这题我一开始有点懵,分析了条件后还是不知道怎么分配比较完美,一开始想一直给最小的那个分配呗,但这不知道分配的力量是多少,没有一个界线,所以要找一个界线,最后还是看了别人的参考答案,用二分确定会变的界线,然后bool数组检查有没有达到界线,没达到的都分配力量,分配的力量要消耗的精力应该选最小值。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int A[1000009];//N名士兵 
int B[509];//M个训练计划 
int C[509];//每个训练计划消耗的精力 
int dp[100009];//dp[i]表示获得至少i点力量所需要的最少精力 
int N,M,K;

bool check(int mid)
{
    ll ans=0;
    for(int i=1;i<=N;i++)//枚举每个士兵的初始力量值 
    {
        //若当前士兵的初始力量值小于mid,说明要消耗精力去训练他,使他获得mid-A[i]点力量
        //同时累加训练该士兵所消耗的最少精力,即dp[mid-A[i]] 
        if(A[i]<mid)ans=ans+dp[mid-A[i]];
    }
    //累加完毕后检查所消耗的总精力是否超出K,若未超出说明该方案可行,否则不可行 
    if(ans<=K)return true;
    else return false;
}

int main()
{
    cin>>N>>M>>K;
    for(int i=1;i<=N;i++)cin>>A[i];
    for(int i=1;i<=M;i++)cin>>B[i];
    for(int i=1;i<=M;i++)cin>>C[i];
    
    memset(dp,0x3f,sizeof(dp));//dp数组先初始化为一个极大值,代表最少消耗的精力为无穷大,后续再缩小 
    dp[0]=0;//获得0点力量,无需消耗精力 
    
    for(int i=1;i<=M;i++)//依次考虑每个计划 
    {
        for(int j=0;j<100009;j++)//枚举所有能获得的力量点数 
        {
            //不选择当前计划,消耗的精力为dp[j] 
            //选择当前计划,若当前能获得的力量点数大于该计划的力量点数,则消耗的精力为dp[j-B[i]]+C[i]
            //若当前能获得的力量点数不大于该计划的力量点数,则消耗的精力为dp[0]+C[i]
            //二者取较小值,更新dp数组 
            dp[j]=min(dp[j],dp[max(0,j-B[i])]+C[i]); 
        }
    } 
     
    //下面开始二分,枚举每个士兵所有可能获得的力量点数,找出下限值
    //初始区间:最少获得1点力量,保险起见右端点可以选大一点 
    int left=1,right=100008;
    while(left<=right)
    {
        int mid=(left+right)/2;//计算中间值 
        if(check(mid))left=mid+1;//若返回true,该方案可行,则取右半区间继续验证 
        else right=mid-1;//不可行,取左半区间继续验证 
    } //退出循环时left已经移至right右侧 
    if(check(left))cout<<left<<endl;//最后验证一遍left是否可行 
    else cout<<left-1<<endl;
    return 0;
}

我的做题感悟:

首先还是这种要分配的问题,多的还是用背包来做,在这个问题中,背包的“容量”可以类比为总精力消耗 K,而每个“物品”的价值和重量则对应于训练计划提升的力量和消耗的精力。在bool函数中不需要急切的去找到dp数组的最小值,而在主函数中去完成,还有一点也是才明白的:写循环的时候什么时候从1开始,什么时候从0开始,这题为了对应士兵编号所以从1开始,后面也有一个=号。这题也是用了二分方法来查找最好的力量界线。

在题目出现这种最佳分配之类的时候,要考虑用到dp,背包,找一个最佳分配界线时考虑二分法

标签:背包,int,精力,兵营,界线,力量,分配,dp
From: https://blog.csdn.net/yyyy2711/article/details/141874609

相关文章

  • 每日OJ_牛客_最长公共子序列(dp模板)
    目录牛客_最长公共子序列(dp模板)解析代码牛客_最长公共子序列(dp模板)最长公共子序列__牛客网解析代码子序列即两个字符串中公共的字符,但不一定连续。        从题干中可以提取出问题:求字符串s和t的最长公共子序列假设LCS(m,n)为长度为m的字符串s与长度为n的......
  • zdppy+vue3+onlyoffice文档管理系统实战 20240902 上课笔记 登录功能优化
    遗留问题1、登录以后跳转最近文档2、如果用户没有登录应该自动跳转登录页面3、如果用户的token校验失败,应该自动调整登录界面4、按回车键自动跳转登录页面登录以后跳转最近文档constrouter=useRouter()router.push("/")实际代码:constloginData=awaitapi.login......
  • winform实时获取系统dpi
    环境:window10框架:4.5.2由于windows10的DPI设置无法直接获取屏幕的真实长宽获取长宽代码intiH=Screen.PrimaryScreen.Bounds.Height;intiW=Screen.PrimaryScreen.Bounds.Width;两种方法:1、使用上边代码获取缩放后的长宽iH*DPI(1.25)=真实高度DPI获取方法:#reg......
  • 产品经理必看!超详细的NPDP认证考试科普
    能力提升是每个职场人最关心的问题,产品经理当然也不例外。相信不少朋友在走上产品的道路后都是边做边学边摸索。特别是刚工作5年内的PM,对产品的整个知识框架并不成熟,1000个产品经理,就有1000个产品问题。但所有问题的本质,都是因为缺少系统的产品管理知识体系、解决问题的原则方法、......
  • 产品经理必看!超详细的NPDP认证考试科普
    能力提升是每个职场人最关心的问题,产品经理当然也不例外。相信不少朋友在走上产品的道路后都是边做边学边摸索。特别是刚工作5年内的PM,对产品的整个知识框架并不成熟,1000个产品经理,就有1000个产品问题。但所有问题的本质,都是因为缺少系统的产品管理知识体系、解决问题的原则方法、......
  • HivisionIDPhotos :一款开源的轻量级且高效的AI证件照制作工具
    HivisionIDPhotos是一款开源的轻量级且高效的AI证件照制作工具,它通过AI算法实现了对多种用户拍照场景的识别、抠图以及证件照生成。这款工具能够根据不同的尺寸规格生成标准证件照和排版照,适用于护照、签证等多种用途。HivisionIDPhotos的主要特点包括轻量级抠图、生成标准证......
  • ModbusTCP 转 Profibus DP(M)网关,型号 SG-TCP-Profibus(M),详细介绍
    一、功能概述1.1设备简介本产品是ModbusTCP和DP(ProfibusDP)网关,使用数据映射方式工作。本产品在ModbusTCP侧作为ModbusTCP从站,接PLC、上位机、wincc屏等;在DP侧做为DP主站,接ProfibusDP设备,如编码器、流量计、显示屏等;通过增加DP/PA耦合器可接入Profi......
  • 镭速UDP测速集成动态库或者静态库测速篇
    1. 下载镭速UDP集成库首先下载镭速UDP集成压缩包,解压后能在解压目录找到三个依赖库RaySync.lib、RaySync-Multi-Proxy-Client-Plus.lib、RaySync-Proxy-Server-Lib.lib。三个依赖头文件TyphoonMultiSocks.h、TyphoonProduct.h、TyphoonServer.h。2. 代码集成接口函数调用顺序:1. ......
  • 第八章 【前端】Mock.js(8.3)——数据占位符定义规范 DPD
    8.3数据占位符定义规范DPDMock.Random是一个工具类,用于生成各种随机数据。Mock.Random类中的方法在数据模板中称为『占位符』,书写格式为@占位符(参数[,参数])。占位符的格式为:'属性名':@占位符Mock.Random类中提供的完整方法(占位符)如下:Type(类型)Method(占......
  • 树形DP学习总结
    学完换根不久后发现不太熟了,赶紧写篇总结复习一下\(\\\\\)树形DP,即在树上进行DP的操作。例题1:luoguP1352没有上司的舞会题目描述某大学有\(n\)个职员,编号为\(1\ldotsn\)。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。......