HDU多校第六场 1007 Getting Your Money Back —— DP + 单调优化_综合

题目链接：点我啊╭(╯^╰)╮

题目大意：

    你的银行账户余额在 $[x, y]$ 范围内
    你需要把它全部取出来，若取 $x$
    若当前余额 $\geq x$ ，则耗费 $a$ 元取出 $x$
    若当前余额 $＜ x$ ，则耗费 $b$ 元，取出失败
    问全取出最坏情况下的最低耗费

解题思路：

    假设 $a = = b$ ，那么很明显是二分
    每次取中点，这样一定最贪心
    问题在于 $a \neq = b$ ，那么中点就不一定是最贪心的
    所以要枚举中间每一个点

    发现答案与区间长度 $y ? x$ 有关，与 $[x, y]$ 无关
    但是发现 $x = 0$ 时，当我们取到 $1$ 时，无论成功失败， $0$ 都不需要再取
    如果余额在 $[1, y]$ ，当我们取到 $2$ 时，如果失败，还要取 $1$
    所以分两种情况DP：
     $d p [i] [0]$ 表示左端点为 $0$ ，长度为 $i$ 的答案， $d p [i] [1]$ 则表示左端点不为 $0$
     $d p [i] [0] = m i n (m a x (d p [j ? 1] [0] + b, d p [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))$

枚举 $j$ ，若 $j$ 失败，则范围变为 $[x, j ? 1]$
若 $j$ 成功，则变为 $[j ? j, i ? j] = [0, i ? j]$

    这样的 $d p$ 是 $n^2$ 的，很明显看出来区间长度越长，答案越大
    也就是 $d p [i] [0]$ 单调不减，那么 $m a x$ 里的函数就是一个单调不增，一个单调不减
    所以 $m a x (d p [j ? 1] [0] + b, d p [i ? j] [0] + a)$ ，就是先减后增
    所以对与某一个 $i$ ，设其决策点为 $j$
    易得对于 $＞ i$ 的点，其决策点 $j$ 只会往后移
    均摊时间复杂度： $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]);}
}