2020-05-24
491 字
2 分钟
UFPE Starters Final Try-Outs 2019 Problem L
链接
题目大意：给定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（某时
2020-05-02
6 字
1 分钟
建站
花了许多时间
