tp题面 前言 作为一个ACGO新蒟蒻,有幸AC掉一道绿题,大喜,遂有此题解 (孩子们我说一石三鸟有没有懂的) 分析 DP部分 这道题如果不考虑输出答案的话,就是一道二维01背包问题. 二维01背包问题本质上仍是一种01背包,只是代价的维度多了一维;放到本题,就是说代价包括重力、阻力这两个维度. 好啊,他升维我也升维.在转移时多加一维,就可以按01背包问题解决了. 于是我们可以写出这样的搜索代码: 如果不考虑输出方案,且硬性要求字典序最小的条件,我们似乎可以AC样例了; 但是很可惜,这题还要输出方案并且要求字典序最小,而经过本蒟蒻1h的调试后,发现这代码很难输出正确方案(乱搞才有20分),于是便只能放弃. (所以最终还是回到了For循环的怀抱) 言归正传,定义f[i][j][k]f[i][j][k]f[i][j][k]为用前iii个中的物品重jjj阻力kkk的时间最大值 仿照01背包,我们不难写出状态转移方程: f[i][j][k]=max(f[i−1][j][k],f[i−1][j−a[i].g][k−a[i].f]+a[i].t);f[i][j][k] = max(f[i-1][j][k],f[i-1][j-a[i].g][k-a[i].f]+a[i].t);f[i][j][k]=max(f[i−1][j][k],f[i−1][j−a[i].g][k−a[i].f]+a[i].t); 同样类比01背包,发现可以滚动数组优化,于是压掉一维,成为: f[j][k]=max(f[j−a[i].g][k−a[i].f]+a[i].t,f[j][k])f[j][k] = max(f[j-a[i].g][k-a[i].f]+a[i].t,f[j][k])f[j][k]=max(f[j−a[i].g][k−a[i].f]+a[i].t,f[j][k]) 然后.就到最恶心的输出方案了. 输出方案 这里我们开个book数组, book[i][j][k]:是否在重力为j、阻力为k的方案中选了第i个物品,book[i][j][k]=1是选了,等于0是没选book[i][j][k]:是否在重力为j、 阻力为k的方案中选了第i个物品,book[i][j][k] = 1是选了,等于0是没选book[i][j][k]:是否在重力为j、阻力为k的方案中选了第i个物品,book[i][j][k]=1是选了,等于0是没选 然后,从最后一个物品开始由最终状态逆推:是否在重力为m、阻力为v的方案中选了第i个物品 如果选了,就令mmm减去对应物品的重力,vvv减去对应物品的阻力. 什么,要求字典序最小? 可以,我们需要将状态转移方程改为这个: f[j][k]=f[j−a[i].g][k−a[i].f]+a[i].t (if f[j][k]<=f[j−a[i].g][k−a[i].f]+a[i].t))f[j][k] = f[j-a[i].g][k-a[i].f]+a[i].t \ (if \ f[j][k] <= f[j-a[i].g][k-a[i].f]+a[i].t))f[j][k]=f[j−a[i].g][k−a[i].f]+a[i].t (if f[j][k]<=f[j−a[i].g][k−a[i].f]+a[i].t)) CODE 主体: 输出: 时间复杂度与空间复杂度:O(nmv)O(nmv)O(nmv) 后记 如果你做对了这题，可以tp到洛谷P1759去,链接：hack传送门