2.4k 2 分钟

链接 题目大意:现在有n个房子,从1到n从左向右排列。每个房子有一个高度,一个人要向通过这个房子,他的高度必须和房子的高度完全相等。你可以修改一个人的身高,给定你一个D,你能使一个人的身高最多增加D或最多减少D。 现在给定你次询问。询问类型1,将一个指定房子的高度修改成其他值。询问类型2,若一个人从一个房子出发,你的修改身高能力的上限为D(每通过一个房子可以修改一次),那么这个人在最远在哪个房子停下来? 房子的高度没什么用,真正有用的是相邻房子的高度差值。因此我们可以搞个绝对值差分数组存储相邻房子的高度差。然后我们可以直接暴力。而这里暴力会超时。我们可以观察,如果此人在第i个房子开始,到第j个...
1.3k 1 分钟

链接 题目大意:给定n个饭盒,和q次询问,每个饭盒拥有美味值v,代价w,取走时间e。每次询问包含一个时间t,和代价上限k。问再此时间,此代价下,能获得的最大美味值是多少? 背包问题,dp[i][j]表示当前可以取走i件物品,且代价为小于等于j可获得的最大值。那么在这问题里,最直接的方法就是选出符合条件的饭盒进行背包DP,但是这会超时。 其实我们只需要把饭盒按照取走时间降序排序,然后做一遍背包DP,这样dp数组的物品维度使按照取走顺序排列的。(dp[1]代表对最后被拿走的物品进行DP,dp[2]代表最后一个和倒数第二个被取走的物品进行DP,以此类推)然后用二分法确定DP[i][j]中的i(某时间...