本文主要是介绍HDU多校第六场 1007 Getting Your Money Back —— DP + 单调优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:点我啊╭(╯^╰)╮
题目大意:
你的银行账户余额在 [ x , y ] [x,y] [x,y] 范围内
你需要把它全部取出来,若取 x x x
若当前余额 ≥ x ≥x ≥x,则耗费 a a a 元取出 x x x
若当前余额 < x <x <x,则耗费 b b b 元,取出失败
问全取出最坏情况下的最低耗费
解题思路:
假设 a = = b a == b a==b,那么很明显是二分
每次取中点,这样一定最贪心
问题在于 a ≠ b a ≠ b a=b,那么中点就不一定是最贪心的
所以要枚举中间每一个点
发现答案与区间长度 y − x y-x y−x 有关,与 [ x , y ] [x,y] [x,y] 无关
但是发现 x = 0 x = 0 x=0 时,当我们取到 1 1 1 时,无论成功失败, 0 0 0 都不需要再取
如果余额在 [ 1 , y ] [1,y] [1,y] ,当我们取到 2 2 2 时,如果失败,还要取 1 1 1
所以分两种情况DP:
d p [ i ] [ 0 ] dp[i][0] dp[i][0] 表示 左端点为 0 0 0 ,长度为 i i i 的答案, d p [ i ] [ 1 ] dp[i][1] dp[i][1] 则表示左端点不为 0 0 0
d p [ i ] [ 0 ] = m i n ( m a x ( d p [ j − 1 ] [ 0 ] + b , d p [ i − j ] [ 0 ] + a ) ) dp[i][0] = min( max(dp[j-1][0] + b, dp[i-j][0] + a) ) dp[i][0]=min(max(dp[j−1][0]+b,dp[i−j][0]+a))
d p [ i ] [ 1 ] = m i n ( m a x ( d p [ j − 1 ] [ 1 ] + b , d p [ i − j ] [ 0 ] + a ) ) dp[i][1] = min( max(dp[j-1][1] + b, dp[i-j][0] + a) ) dp[i][1]=min(max(dp[j−1][1]+b,dp[i−j][0]+a))
枚举 j j j ,若 j j j 失败,则范围变为 [ x , j − 1 ] [x,j-1] [x,j−1]
若 j j j 成功,则变为 [ j − j , i − j ] = [ 0 , i − j ] [j-j, i-j] = [0, i-j] [j−j,i−j]=[0,i−j]
这样的 d p dp dp 是 n 2 n^2 n2 的,很明显看出来区间长度越长,答案越大
也就是 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 单调不减,那么 m a x max max 里的函数就是一个单调不增,一个单调不减
所以 m a x ( d p [ j − 1 ] [ 0 ] + b , d p [ i − j ] [ 0 ] + a ) max(dp[j-1][0] + b, dp[i-j][0] + a) max(dp[j−1][0]+b,dp[i−j][0]+a) ,就是先减后增
所以对与某一个 i i i ,设其决策点为 j j j
易得对于 > i >i >i 的点,其决策点 j j j 只会往后移
均摊时间复杂度: O ( n ) O(n) O(n)
核心:DP + 单调优化
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int T, x, y, a, b;
ll dp[maxn][2];ll slope0(int j, int i){return max(dp[j-1][0] + b, dp[i-j][0] + a);
}
ll slope1(int k, int i){return max(dp[k-1][1] + b, dp[i-k][0] + a);
}int main() {scanf("%d", &T);while(T--){scanf("%d%d%d%d", &x, &y, &a, &b);int n = y - x;dp[0][0] = 0, dp[0][1] = a;for(int i=1, j=1, k=1; i<=n; i++){while(j<i && slope0(j+1, i) <= slope0(j, i)) j++;while(k<i && slope1(k+1, i) <= slope1(k, i)) k++;dp[i][0] = slope0(j, i), dp[i][1] = slope1(k, i);}printf("%lld\n", dp[n][x>0]);}
}
这篇关于HDU多校第六场 1007 Getting Your Money Back —— DP + 单调优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!