CUST程序设计天梯赛校赛 L2-2 power

应某位大佬的要求,来写题解了.但是我太菜了,只能写写简单题.
大致思路: 题目乍一看是个完全背包问题 (实际上也确实是),但多了一层限制, 即每次玩的项目不能比上一次便宜 ,所以其实就在完全背包问题的基础上,进行修改.
板子的完全背包, 考虑第i个物品时,所用的dp[]数组,所代表的含义是前i-1个物品都考虑进去,所形成的最优解,但是这个题目在第i个物品时,不能把前i-1个全考虑进去,只能在前面所有价格v比它小的所形成的最优解的前提下,进行更新.
好在数据n很小,所以我们可以开一个二维dp数组,dp[i][j]表示以第i个物品为结尾,容量为j时的最优解然后暴力枚举前i-1个数的v[k],如果v[k]<=v[i],那么就在dp[k]的基础上对dp[i]进行更新.
【CUST程序设计天梯赛校赛 L2-2 power】虽然思路上是枚举前i-1个,但是不要忘了,本身第i个这个物品自己就可能不以前面为基础,就只靠自己形成最优解,所以在前面i-1个考虑完之后,还要考虑自身.所以就干脆在k的那层循环里,考虑前i个数.
注意事项: 亲身惨痛经历:debug了一个多小时.
首先,状态转移方程.若第k个数满足v[k]<=v[i]时,那么这是dp[i][j]就有四种可能.dp[i][j]=dp[i][j],dp[i][j]=dp[k][j],dp[i][j]=dp[i][j-v[i]+w[i],dp[i][j]=dp[k][j-v[i]+w[i].

然后,还有一件事.由于dp[i][m]表示的是,以i为结尾的,所有组合的最优解,所以和正常的背包问题不同的是,dp[n][m]不一定是所有组合的最优解,因为可能最终的最优解,是不包含第n个物品的.
所以,最后要在遍历一边1~n,比较所有的dp[i][m],选其中的最大值.
AC代码 #includeusing namespace std;const int N = 3000 + 10;typedef pair pi;typedef long long ll;const int inf = 0x3f3f3f3f;ll n; ll l, r;ll m, x, c, p;ll len;int v[N];int w[N];int dp[60][N];int main() { cin >> n >> m; for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i]; } //考虑第i个物品时,将其前面所有的比他小的dp都拿来用一遍for (int i = 1; i <=n; i++) {for (int k = 1; k <= i; k++) {//k枚举i前比他小的数if (v[k] <= v[i]) {for (int j = v[i]; j <= m; j++) {//j枚举容量,因为是完全背包,所以从v[i]开始dp[i][j] = max(max(dp[i][j], dp[k][j]), max(dp[k][j - v[i]] + w[i], dp[i][j - v[i]] + w[i]));//四种选择:此次不选,本身不变,此次不选,跟第k个一致,此次选,跟dp[k]有关,此次选,跟dp[i]有关.}}}}//最后遍历所有的dp[i][n]int ans = 0;for (int i = 1; i <= n; i++) ans = max(ans, dp[i][m]);cout << ans;}
最后当然,因为是菜鸡写的,所以可能还有优化的空间,勿喷.
若看完这篇之后,能有收获,感谢yxh大佬吧.