分类 斜率优化 DP 下的文章

BZOJ 1010: [HNOI2008]玩具装箱toy

Solution按照套路推式子就可以了...维护一个斜率递增的凸包。Code#include <cstdio> #include <algorithm> #define long long long using namespace std; const int N = 5e4 + 10; int n, c; long s[N]; long f[N]; double pow(double x) {return x * x;} long pow(long x) {return x * x;} double g(int x) {return s[x] + - 阅读剩余部分 -

BZOJ 1911: [Apio2010]特别行动队

Solution斜率优化第一题,写个博客记录一下吧,首先根据题意能列出一个 $O(n^2)$ 的转移方程,其中 $s[i]$ 表示前 $i$ 个数的和。$$ f[i] = max( f[j] + a * (s[i] - s[j])^2 + b * (s[i] - s[j]) + c ) $$看一下数据范围 n 在 1e6 左右, $O(n^2)$ 肯定是超时的,考虑斜率优化。假设当前要求 $f[i]$,并且存在两个状态 $j1 < j2$ 可以转移,如果 $j2$ 更优的话,我们需要满足:$$ f[j1] + a * (s[i] - s[j1])^2 + b * (s- 阅读剩余部分 -