首页 > 其他分享 >[ARC096F] Sweet Alchemy

[ARC096F] Sweet Alchemy

时间:2023-07-05 14:36:36浏览次数:55  
标签:背包 Sweet Alchemy ARC096F 物品 贪心

[ARC096F] Sweet Alchemy

洛谷:[ARC096F] Sweet Alchemy

Atcoder:[ARC096F] Sweet Alchemy

Solution

将原题限制转化为父节点 \(p_i\) 向子节点 \(i\) 连边,把选取单点转化为选取子树,相当于做了一次差分,这样选取任意一个点的子树的次数都不能超过 \(d\)(根节点对应的整棵树除外)

这是一个显然的多重背包问题:选取一个子树 \(T\),对应体积 \(v_i = \sum\limits_{x \in T}m_x\),价值 \(w_i = size_T\),最多选 \(d\) 次(根节点对应的整棵树除外)。

但是体积和物品数量都是 \(10^9\) 级别的,常规的多重背包根本没法做。

贪心

这个题最厉害的地方就是把背包和贪心结合在一起。

众所周知,按 \(\frac{w_i}{v_i}\) 从大到小排序尽量多选的方法是错误的,但不妨考虑这个贪心在什么时候是对的。

尽可能地把绝大多数规模的问题划归到一个正确的贪心上以保证时间复杂度正确。

假设现在有物品 \(i, j\),\(\frac{w_i}{v_i} > \frac{w_j}{v_j}\),即 \(w_iv_j > w_jv_i\),可以看作是选 \(w_i\) 个 \(j\) 物品的体积大于选 \(w_j\) 个 \(i\) 物品的体积。同时两种选取方式的价值都是一样的,为 \(w_iw_j\),因此 选 \(w_j\) 个 \(i\) 物品一定优于选 \(w_i\) 个 \(j\)​ 物品

当选择的 \(i\) 物品数量超过 \(w_j\) 个时,\(j\) 物品最多选 \(w_i - 1\) 个。

记 \(c_x\) 表示物品 \(x\) 的选取个数,则不可能出现 \(c_i \le d - w_j\) 且 \(c_j \ge w_i\) 的情况,因为可以把 \(w_i\) 个 \(j\) 物品换成 \(w_j\) 个 \(i\) 物品。

借洛谷题解里的这个图:

可知中间部分的贪心是正确的,也即中间部分不可能有两个没填满的柱子。

把每个物品取 \(\min(d, n)\) 个出来做多重背包(\(n\) 对应物品价值的上界),剩下的就按 \(\frac{w}{v}\) 从大到小能选就选。

此时多重背包价值和的上界为 \(n^3\),于是背包时将价值与体积倒过来处理。

code \(O(n^5)\)

标签:背包,Sweet,Alchemy,ARC096F,物品,贪心
From: https://www.cnblogs.com/Schucking-Sattin/p/17528418.html

相关文章

  • Flask SQLALCHEMY Model 模型
    FlaskSQLALCHEMYModel模型classPerson(db.Model): __tablename__='person' id=db.Column(db.Integer,primary_key=True) name=db.Column(db.string(16),unique=True) def__repr__(self):return'<User{}>'.format(self......
  • Flask SQLAlchemy配置
    FlaskSQLAlchemy配置Flask模型Flask默认并没有提供任何数据库操作的API我们可以选择任何适合自己项目的数据库来使用Flask中可以自己的选择用原生语句实现功能,也可以选择ORM(SQLAlchemy,MongoEngine)原生sQL缺点代码利用率低,条件复杂代码谐句越长,有很多相似语句......
  • 使用 SQLAlchemy 库来实现对 MySQL 数据库的增删改查
    在 Flask 中使用SQLAlchemy库来实现对MySQL数据库的增删改查fromflaskimportFlask,request,jsonifyfromflask_sqlalchemyimportSQLAlchemyapp=Flask(__name__)app.config['SQLALCHEMY_DATABASE_URI']='mysql://username:password@localhost/dbname'ap......
  • sqlalchemy: pool_pre_ping
    问题设想这样一个场景:通过flask启动了一个REST服务,该服务需要访问数据库,且每天被定时请求一次(除此之外无请求)。按照上一节的讨论,由于两次请求间隔(24小时)超过了关闭阈值(8小时),因此在下一次发送请求时,会报出Lostconnection的错误。解决方案一个可选的解决方案是,增加wait_timeout......
  • AtCoder Beginner Contest 281 Ex Alchemy
    洛谷传送门AtCoder传送门考虑设\(f_i\)为\(i\)的答案,那么:\[f_i=[x_i](1+x)^A\prod\limits_{j=2}^{i-1}(1+f_jx)\]这个东西其实是可以分治FFT的。具体地,设分治区间为\([l,r]\),要求一个\(r-l+1\)次多项式\(\prod\limits_{i=l}^r(1+f_ix)\)。......
  • 关于SQLAlchemy中update的使用参数synchronize_session
    update语句带上synchronize_session="fetch"或者带上synchronize_session=False是啥区别在SQLAlchemy中,当您使用update语句更新数据库中的记录时,可以使用`synchronize_session`参数来指定要同步的会话对象。-当`synchronize_session`设置为`False`时,会话对象不会自动同步,这意......
  • sqlalchemy.orm.exc.DetachedInstanceError: Instanceis not bound to a Session; att
    在使用sqlalchemy的orm时,在一个循环中,如果一开始select时用了session,中间update某条记录后,session被关闭,就会出现对象notboundtoaSession的问题.DBSession=sessionmaker(bind=self.engine,expire_on_commit=False)这时需要 expire_on_commit=False Themostcommo......
  • flask_SQLAlchemy 出现了 Lost connection to MySQL server during query Mysql主机连
    使用pythonflask框架 flask_sqlalchemy时出现了LostconnectiontoMySQLserverduringqueryMysql主机连接超时的问题由于Mysql会定时处理长时间未连接使用的连接池具体时长可通过查看showvariableslike'%timeout%' wait_timeout为超时时长,这里的时间时120秒......
  • SQLAlchemy介绍
    SQLAlchemy介绍SQLAlchemy是一个基于Python的ORM框架。该框架是建立在DB-API之上,使用关系对象映射进行数据库操作。简而言之就是,将类和对象转换成SQL,然后使用数据API执行SQL并获取执行结果。补充:什么是DB-API?是Python的数据库接口规范。在没有DB-API之前,各数据库之间的应用......
  • Python数据库篇:sqlite3、mysql、sqlalchemy
    一:sqlite3importsqlite3conn=sqlite3.connect("test.db")cursor=conn.cursor()cursor.execute("createtableuser(idvarchar(20)primarykey,namevarchar(20))")cursor.execute("insertintouser(id,name)values(\'1\�......