贪心(微扰) + dp
这道题还是比较难的,前置知识:
算法1:暴力$O(T * n! * n)$
可以$dfs$全排列枚举所有吃的方案,然后每次线性算能量取最大值即可。
算法2:贪心 + dp $O(T * n * \sum_{i = 1}^{n}s_i)$
贪心将问题转化
发现有可能存在最优解的某些宝石的贡献为$0$,我们剔除了这些宝石。
假设最优解的能量石排列长度为$k (1 <= k <= n)$ 因为去掉了那些没有贡献的宝石,位置为:
$a_1, a_2, a_3…a_k$。
那么对于任意两个位置$i = a_l, j = a_{l + 1} (1 <= l < k)$
交换后两个宝石的贡献总和不会变得更大,即(假设之前的总时间为$t$ ):
$E_i - t * L_i + E_j - (t + S_i) * L_j >= E_j - t * L_j + E_i - (t + S_j) * L_i$
整理后:
$S_i * L_j <= S_j * L_i$。
我们可以把跟$i$有关的放到一边,调整一下:
$\frac{S_i}{L_i} <= \frac{S_j}{L_j}$
这样,我们只要以如上条件作为宝石间排序的条件,进行一次$sort$。
因为对于其他形式的放置规律,必然可以通过交换满足$\frac{S_i}{L_i} > \frac{S_j}{L_j}$的相邻的两项来得到更小值。
那么最优解的坐标(新的坐标)一定满足:
$a_i < a_2 < a_3 … < a_k$
dp
那么,我们只要搞个$01$背包,$S_i$作为费用,$max(0, E_i - (t - S_i) * L_i)$ 作为价值 ($t$为当前花费时长)。
$f[t]$ 表示当前正好花$t$时间得到的最大能量。
状态转移方程:
$f[t] = max(f[t], f[t - S_i] + max(0, E_i - (t - S_i) * L_i))$
由于我们背包放物品(宝石)的顺序是坐标从$1$到$n$的,所以一定能枚举到最优解。
初始状态:$f[0] = 0$,其余为负无穷
答案:$max(f[i]) (1 <= i <= \sum_{i = 1}^{n}s_i)$
参考代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105, S = 10005;
int n;
int f[S];
struct Node{
int s, e, l;
bool operator < (const Node &x) const{
return s * x.l < x.s * l;
}
}a[N];
int main() {
int T, cnt = 0; scanf("%d", &T);
while(T--) {
memset(f, 0xcf, sizeof f);
scanf("%d", &n);
int t = 0;
for(int i = 1, s, e, l; i <= n; i++) {
scanf("%d%d%d", &s, &e, &l);
t += s; a[i] = (Node) { s, e, l };
}
sort(a + 1, a + 1 + n);
f[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = t; j >= a[i].s; j--)
f[j] = max(f[j], f[j - a[i].s] + max(0, a[i].e - (j - a[i].s) * a[i].l));
}
int res = 0;
for(int i = 1; i <= t; i++) res = max(res, f[i]);
printf("Case #%d: %d\n", ++cnt, res);
}
return 0;
}
sort将排列数优化为组合数,组合数就可以用背包了,妙啊!
呃,哥们你是没听课吗?
....
有点不理解。照理来讲,背包问题其实本质是选择出一个最优的子序列。难道不会存在这样的一个情况:当我们交换之后,子序列的选法也会发生变化(由于有时间消耗,导致原序列也会发生改变,做最优决策的时候就会导致各个物品的选法不同)。也就是说交换邻项的操作实际上是会影响其他位置的决策的。
所以,这个证明我感觉有一些问题。或者说,是我哪里欠考虑了。
选相邻的两项就是为了不影响,对于i之前的和j之后的列表,开始的时间没有发生变化。
你只能按照排好序的序列来选取子序列
有一个问题,为什么排序的时候,不考虑,Ej−(Si)∗Lj为0这样的情况。虽然考虑和不考虑最终对答案没影响。
bool cmp(node A,node B)
{
int a1 = A.a,b1 = A.b,c1 = A.c;
int a2 = B.a,b2 = B.b,c2 = B.c;
int sum1 = b2-a1c2,sum2 = b1-a2c1;
if(sum1!=0&&sum2!=0) return c1a2>c2a1;
else if(sum1==0&&sum2!=0) return a2c1>b2;
else if(sum1!=0&&sum2==0) return b1>a1c2;
else return b1>b2;
}
我考虑了,结果一直不过,删掉这段代码,就通过了,很奇怪
orz
应该是
吧
如果定义为不超过j的最大价值 然后再创建一个cnt[i][j]存储所消耗的实际时间 为什么还不能做
为什么最后要再重新枚举一遍才能得到答案
因为是状态是使用时间恰好为j 使用j1时间有一个最优解 使用j2时间有一个最优解 还要比较j1和j2两个最优解 哪一个是整体最优解
我觉得是题目并没有要求每一块石头都得吃,所以最后的时间并不一定是吃所有石头的方案,需要枚举一遍0 ~ 吃完所有石头的时间。
是不是含在口中的能量不会随时间逐渐递减啊???
正确的
”交换后两个宝石的贡献总和不会变得更大,“ 这句话,对于最优解交换两个位置为什么不会变得更大????
因为是最优解
就是说,我们有办法找到这样一种排列方式,使得“交换后两个宝石的贡献总和不会变得更大”。而在其他某些问题中,这种排列可能并不存在,这才是问题的关键。
巨巨 y总代码里面没有将
e - (j - s) * l
和0
取max,是为什么呢?是因为即使e - (j - s) * l < 0
了也不会影响正确情况的产生吗?同样有这个问题?
同问,想不通
小于最优的j更低吧也能取到
同问,想不通
最优解里肯定不用吃能量为0的石头
我考虑了,结果一直不过,删掉这段代码,就通过了,很奇怪
这个
int w=e - (j - s) * l
表示的是获益,而且是求的获益的最大值,如果w是负值,大不了不从它转移就可以了,负的就负的吧。想问问大佬如果定义f[i][j]为前i个物品取j个的最大能量,time[i][j]为f[i][j]达到最优解所需要的时间.
f[i][j] = max(f[i-1][j],f[i-1][j-1]+s[i].e - time[i-1][j-1]*s[i].l) 这样的状态转移方程为什么会错呢?
看了一圈题解都是和大佬差不多的写法orz
你反过来不是要时间越少越好吗
意思是时间会影响结果,所以要作为f数组的一维状态吗?本蒟蒻没怎么看懂QAQ…
我也不怎么看懂你说的啊
😂大佬你说时间是越少越好,所以我想时间作为一个影响res的因素,是否是一定要f数组增加一维记录它.
所以这道题不能写成前i个取j个,因为没有考虑时间.不知道这样理解对不对?😂
俺感觉调换体积和价值是挺可以写的吧,就是比如f i j 表示获得j能量最小的时间这样转移感觉挺有理有据的
那么限制条件要么作为f数组的下标,要么作为f数组的值,不知道是不是这样
感觉我把这道题和一道状压dp搞混了
总之感谢大佬回复,困扰我很久总算搞懂了一点😂~
不排序 直接01背包 可以吗
不行
请问下DP问题中什么时候用f[j]表示当体积正好为j时的最大值和体积最多为j时的最大值呢?感觉这两种情况下好像状态转移方程是一样的
选相同的物品,如果 $j$ 增加了结果可能变差,也就是这题的价值和 $j$ 有关,所以还是设状态正好为 $j$ 比较好处理。最多为 $j$ 的话最后仍需要取最大值
请问为什么j增加了结果会变差呢…我试了一下的确是错的,不是很理解0.0
关键是你看那个转移方程
$max(0, E_i - (t - S_i) * L_i)$
这个花费是依赖于当前的体积j的,所以说如果你改成至多,这块的花费就算错了。
换了一种解释方法,不知道能不能理解,之前说的有点跳跃
比如最优解是体积是3,那么如果体积最大值是4,你算f[4]的时候j=4,但最优的花费应该是用j=3算
豁然开朗!感谢感谢
这个解释得很好!
我大概想明白了,体积至多为 j :相当于一条定长(背包容量)数轴上,每个物品占据一定的长度(体积),选取出最大价值。但是在这道题里,数轴上物品的选择不能产生空隙,即巨魔在吃下一个能量石不能等待,因为等待会影响下一个能量石的能力衰减,为了避免空隙产生,就用体积恰好为 j 的方案
而且空隙是无法确定的,巨魔上一次开炫的能量石在[1, j] 这一次也在[1, j],我们没办法知道他中间有没有吃,也就无法知道这一次吃的能量石是否发生了衰减
就是当前吃的能量石衰减时间不止巨魔之前吃能量石的时间,可能还有他之前等待时间
请问是如何想到:用体积恰好是j,而不是用体积至多是j的?
因为更新f[j]是以j时间计算能量损耗的,显然j变大不会更优。至多也可以做,没有影响,但是最后仍需要取最大值。
原来如此,受教了Orz