【动态规划】 Little Sub and Piggybank
Problem
Input
Output
Please output an integer in one line, indicating the maximum happiness that Little Sub can achieve.
Sample Input
4 0 2 4 1 0 4 3 1Sample Output
5Solution
你有一个piggybank小猪存钱罐。你在每天的开始都可以向piggybank中放入任意数量的钱，只要放的不比前一天多就行。第一天可以放入任何数量的钱。每天超市都有一个物品，第i天的物品价格为w[i]，购买后得到的愉悦度为v[i]。但是你只有在piggybank中的钱刚好等于w[i]时，才可以买入第i天的物品，买完之后你的钱包就空了。问到第n天，能够获得最大愉悦度是多少。
dp[i][j] 表示当前购买的是i物品，前一个是j物品的最大愉悦度。
显然有转移方程 dp[i][j] = max(dp[j][k] + v[i])。
因为v[i]是定值，所以又可以写成dp[i][j] = max(dp[j][k]) + v[i]。
如果对于给定的i，j，枚举k来找max(dp[j][k])的话，时间复杂度会达到\(O(n^3)\)。
因此我们可以令mx[j][k]表示购买了第j个物品，且购买第j个物品之前购买的一个物品在k到j之间的最大愉悦度。
于是转移方程就可以写成dp[i][j] = mx[j][k] + v[i]。
如果你尝试了\(O(n^3)\)的暴力写法，你就会知道不是所有的k都可以进行状态转移的。因为题目要求每天放入piggybank的钱的数量不能大于前一天放入的数量。所以在i和j确定的情况下，从第j天到第i天放入的钱的数量已经确定，而在第j天放入钱数的最小值应该大于\(\frac{w[i]}{i-j}\)
即 \(\frac{w[j]}{j-k} >= \frac{w[i]}{i-j}\)
移项可以得到 \(k >= j – \frac{w[j]}{w[i]}(i-j)\) ，即为k的最小值。
而如何维护mx[i][j]数组呢？
可以在枚举i的时候用已知的dp[i][j]更新。mx[i][j] = max(mx[i][j+1], dp[i][j]);
最后可以用max(mx[i][0])更新答案。
Code
#include
using namespace std; typedef long long ll; const int MAXN = 2005; ll w[MAXN],v[MAXN]; ll dp[MAXN][MAXN],mx[MAXN][MAXN]; int main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%lld",w+i); for(int i = 1; i <= n; i++) scanf("%lld",v+i); ll ans = 0; //本题中让输入数据的下标从1开始，0空出来看作一个必买入的无价值物品，方便数组的表示。 for(int i = 1; i <= n; i++) { dp[i][0] = v[i]; for(int j = 1; j < i; j++) { int k = ((w[i] == 0) ? 0 : (int)max(ceil(j - 1.0*w[j]/w[i]*(i-j)),0.0)); if(mx[j][k]) dp[i][j] = mx[j][k] + v[i]; //mx[j][k] == 0 说明不往piggybank中放钱了 } for(int j = i - 1; j >= 0; j--) { mx[i][j] = max(mx[i][j+1], dp[i][j]); } } for(int i = 1; i <= n; i++) { ans = max(ans, mx[i][0]); } printf("%lld\n",ans); return 0; }
转载于:https://www.cnblogs.com/NeilThang/p/10809730.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219913.html原文链接：https://javaforall.net
