首页 > 可持久化动态图上树状数组维护01背包
头像 憨憨杰尼二号
发表于 2020-07-15 10:54:27
题目给的数据范围有正数也有负数,所以有意义的删数方案为:对于负数在原位置删除保证下标最大从而使i ai最小化对于正数在下标为1的位置一次删除使i ai最小化下面是代码: #include<bits/stdc++.h> long long num[1000005]; int n; int 展开全文
头像 Clouder0
发表于 2020-07-14 21:32:05
说实话我都不知道可持久化动态图是个啥东西……题目其实是贪心:显然每次删除第一个元素,可以让整体代价最小。但 时,代价是负数,要求最大,那么对于 而言最大的下标就是原始下标。 #include <cstdio> #include <algorithm> #include & 展开全文
头像 sunsetcolors
发表于 2020-07-14 23:13:33
B 可持久化动态图上树状数组维护01背包 题目地址: https://ac.nowcoder.com/acm/contest/6290/B 基本思路: 名字非常的唬人,然而是一个***题,我们先将负数从后往前删,就能保证它们在自己所在的位置被删掉,获得最小的负值,然后再让正数都在第一个位置删 展开全文
头像 东溪看水
发表于 2020-07-15 12:02:18
题目 有一个长度为 序列 (序列下标从 1 开始),每次可以从任意位置 花费 的代价来把 删除。注意,删除后 后面的数会依次向前补上(下标 -1 ) 。求把整个序列删完的最小代价。 解题思路 当 是正数时,在下标 1 的位置删除代价最小,即 。当 是负数时,在其当前所在下标的位置删除代 展开全文
头像 耕云种月
发表于 2022-01-30 18:59:47
原题解链接:https://ac.nowcoder.com/discuss/149990 由题可知,如果该序列均为非负数,则从左向右依次删除最优,代价为各个数之和。 而序列中如果有负数,则先从右向左依次删除每个负数,这样会使代价减小的最多。然后序列就只剩下了非负数,依次删除即可。 #include 展开全文