CodeForces 815C :Karen and Supermarket 树上有依赖背包

2024-04-13 13:18

本文主要是介绍CodeForces 815C :Karen and Supermarket 树上有依赖背包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题目描述

在回家的路上,凯伦决定到超市停下来买一些杂货。 她需要买很多东西,但因为她是学生,所以她的预算仍然很有限。
事实上,她只花了 b b b美元。
超市出售 N N N种商品。第 i i i件商品可以以 c i c_{i} ci美元的价格购买。当然,每件商品只能买一次。
最近,超市一直在努力促销。凯伦作为一个忠实的客户,收到了 n n n张优惠券。
如果凯伦购买 i i i次商品,她可以用i次优惠券降低 d i d_{i} di美元。 当然,不买对应的商品,优惠券不能使用。
然而,对于优惠券有一个规则。对于所有 i > = 2 i>=2 i>=2,为了使用i张优惠券,凯伦必须也使用第 x i x_{i} xi张优惠券 (这可能意味着使用更多优惠券来满足需求。)
凯伦想知道。她能在不超过预算 B B B的情况下购买的最大商品数量是多少?

分析

比较经典的树上有依赖背包问题了,做之前可以先去看一下没有上司的舞会这道题,可能理解起来会更快
f [ i ] [ j ] [ 0 / 1 ] f[i][j][0/1] f[i][j][0/1]表示在 i i i点选了 j j j件商品,是否使用优惠卷的情况下的最小花费,然后状态转移搞一下,最后判断一个最大件数就可以了

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 5010;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
int gcd(int a,int b){return (b>0)?gcd(b,a%b):a;}
int h[N],ne[N],e[N],idx;
int f[N][N][2];
int a[N],b[N];
int sz[N];
int n,li;void add(int x,int y){ne[idx] = h[x],e[idx] = y,h[x] = idx++;
}void dfs(int u){sz[u] = 1;f[u][1][0] = a[u];f[u][1][1] = a[u] - b[u];f[u][0][0] = 0;for(int i = h[u];~i;i = ne[i]){int v = e[i];dfs(v);for(int j = sz[u];j >= 0;j--)for(int k = 0;k <= sz[v];k++){f[u][j + k][0] = min(f[u][j + k][0],f[u][j][0] + f[v][k][0]);f[u][j + k][1] = min(f[u][j + k][1],f[u][j][1] + f[v][k][1]);f[u][j + k][1] = min(f[u][j + k][1],f[u][j][1] + f[v][k][0]);}sz[u] += sz[v];}
}int main(){memset(h,-1,sizeof h);read(n),read(li);memset(f,0x3f,sizeof f);for(int i = 1;i <= n;i++){read(a[i]),read(b[i]);if(i != 1){int u;read(u);add(u,i);}}dfs(1);int ans = 0;for(int i = n;i;i--) if(f[1][i][0] <= li || f[1][i][1] <= li){ans = i;break;}di(ans);return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

这篇关于CodeForces 815C :Karen and Supermarket 树上有依赖背包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/900245

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件?二、我们为什么需要使用whl文件来安装python库?三、我们应该去哪儿下

Spring AI Alibaba接入大模型时的依赖问题小结

《SpringAIAlibaba接入大模型时的依赖问题小结》文章介绍了如何在pom.xml文件中配置SpringAIAlibaba依赖,并提供了一个示例pom.xml文件,同时,建议将Maven仓... 目录(一)pom.XML文件:(二)application.yml配置文件(一)pom.xml文件:首

使用maven依赖详解

《使用maven依赖详解》本文主要介绍了Maven的基础知识,包括Maven的简介、仓库类型、常用命令、场景举例、指令总结、依赖范围、settings.xml说明等,同时,还详细讲解了Maven依赖的... 目录1. maven基础1.1 简介1.2 仓库类型1.3 常用命令1.4 场景举例1.5 指令总结

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、

python中poetry安装依赖

《python中poetry安装依赖》本文主要介绍了Poetry工具及其在Python项目中的安装和使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录前言1. 为什么pip install poetry 会造成依赖冲突1.1 全局环境依赖混淆:1

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<