斜率优化的dp问题算法动态规划java

洛谷P3195 [HNOI2008]玩具装箱题目介绍链接：https://www.luogu.com.cn/prob...
解题报告解法一（TLE）
看到题首先写出暴力版本dp

#include #include typedef long long ll; #define read(x) scanf("%lld", &x)using namespace std; const int N = 50010; ll sumc[N], f[N], n, L; int main() { read(n); read(L); ll c; for (int i = 1; i <= n; i++) { read(c); sumc[i] = sumc[i - 1] + c; } for (int j = 1; j <= n; j++) { f[j] = 0x3f3f3f3f3f3f3f3f; for (int i = 0; i < j; i++) { f[j] = min(f[j], f[i] + (j - i - 1 + sumc[j] - sumc[i] - L) * (j - i - 1 + sumc[j] - sumc[i] - L)); } } cout << f[n]; return 0; }

易知上述解法是O(n^2)的时间复杂度，而该题样例给到了5乘10的4次方，这个解法是会TLE的。因此应该是可以根据动态转移方程优化的。
上述解法提交后和预料的一样，有三个测试点TLE了，但是另外七个测试点AC证明动态转移方程没有问题，因此接下来可以抛开题意专心根据该动态转移方程进行优化
解法二（AC）根据斜率优化
动态转移方程为

f[j] = min(f[j], f[i] + (j - i - 1 + sumc[j] - sumc[i] - L) * (j - i - 1 + sumc[j] - sumc[i] - L));

令
$$ a[i]=sumc[i]+i $$
$$ b[i]=sumc[i]+i+L+1 $$
简化计算
上式可转化为
$$ f[j] = f[i] + (a[j] - b[i]) ^ 2 $$
展开得
$$ f[i]+b[i]^2=2a[j]*b[i]-a[j]^2+f[j] $$
当j确定时，a[j]为常量并且大于0，将f[i]+b[i]^2作为y，b[i]作为x
则可简化为
$$ y=2a[j]*x-a[j]^2+f[j] $$
2a[j] > 0，所以斜率大于0
当y轴截距最小时，f[j]最小

文章图片

将斜率为2a[j]的线向上移，第一个碰到的点即为能使f[j]最小的点，凸包原理得点i处斜率是第一个大于绿线斜率的点
根据凸包原理，只需维护一个凸包即可
这题a[j]也是单调递增的，因此前面不符合的点肯定不会再被用到了，可以直接丢弃，只需维护有限几个点即可
代码如下：

#include #include typedef long long ll; #define read(x) scanf("%lld", &x)using namespace std; const int N = 50010; ll sumc[N], f[N], n, L; ll hh, tt, q[N]; ll A(ll i) { return sumc[i] + i; }ll B(ll i) { return (ll) sumc[i] + i + L + 1; }ll Y(ll i) { return f[i] + B(i) * B(i); }ll X(ll i) { return B(i); }double slope(ll i1, ll i2) { return (double) (Y(i2) - Y(i1)) / (double) ((X(i2) - X(i1))); }int main() { read(n); read(L); ll c; hh = tt = 0; for (int i = 1; i <= n; i++) { read(c); sumc[i] = sumc[i - 1] + c; } for (int j = 1; j <= n; j++) { while (hh < tt && Y(q[hh + 1]) - Y(q[hh]) < (X(q[hh + 1]) - X(q[hh])) * 2 * A(j)) { hh++; } f[j] = f[q[hh]] + (A(j) - B(q[hh])) * (A(j) - B(q[hh])); while (hh < tt && slope(j, q[tt - 1]) <= slope(q[tt], q[tt - 1])) { tt--; } q[++tt] = j; } cout << f[n]; return 0; }

成功AC
P4072 [SDOI2016]征途题目介绍链接：https://www.luogu.com.cn/prob...
解题报告解法一
思考动态转移方程
f[i] [j]表示走了i段现在在j地
上一步为f[i - 1] [k] k可能为0~j-1地
写出以下代码

#include #include #include #include typedef long long ll; #define read(x) scanf("%d", &x)using namespace std; const int N = 3010; int n, m, sum[N]; ll f[N][N]; int main() { read(n); read(m); for (int i = 1; i <= n; i++) { int c; read(c); sum[i] = sum[i - 1] + c; } memset(f, 0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; n - j >= m - i; j++) { for (int k = 0; k < j; k++) { f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k])); } } } ll res = f[m][n] * m - sum[n] * sum[n]; cout << res; return 0; }

提交后可看到由于复杂度较高，有一个样例依然是过不了的
解法二
将动态转移方程移项得：
$$ f[i-1][k] + sum[k] ^2 = f[i,j] + 2* sum[j] * sum[k] - sum[j] ^2 $$
令f[i-1] [k] + sum[k] ^2 = y
sum[k] = x
斜率为2*sum[j] > 0
因为sum[j]为定量，所以使截距最小即可

#include #include #include #include typedef long long ll; #define read(x) scanf("%d", &x)using namespace std; const int N = 3010; int n, m, sum[N], q[N], hh, tt; ll f[N][N]; ll X(int k) { return sum[k]; }ll Y(int i, int k) { return f[i - 1][k] + sum[k] * sum[k]; }double slope(int i, int k1, int k2) { return (double) (Y(i, k1) - Y(i, k2)) / (double) (X(k1) - X(k2)); }int main() { read(n); read(m); for (int i = 1; i <= n; i++) { int c; read(c); sum[i] = sum[i - 1] + c; } memset(f, 0x3f, sizeof f); for (int i = 1; i <= n; i++) { f[1][i] = sum[i] * sum[i]; } f[0][0] = 0; for (int i = 2; i <= m; i++) { hh = tt = 0; for (int j = 1; n - j >= m - i; j++) { while (hh < tt && slope(i, q[hh], q[hh + 1]) < 2 * sum[j]) { hh++; } f[i][j] = f[i - 1][q[hh]] + (sum[j] - sum[q[hh]]) * (sum[j] - sum[q[hh]]); while (hh < tt && slope(i, j, q[tt - 1]) <= slope(i, q[tt], q[tt - 1])) { tt--; } q[++tt] = j; } } ll res = f[m][n] * m - sum[n] * sum[n]; cout << res; return 0; }

成功AC
AcWing Q301 任务安排题目介绍链接：https://www.acwing.com/proble...
解题报告解法一

#include #include #include #include typedef long long ll; #define read(x) scanf("%d", &x) #define read(x, y) scanf("%d%d", &x, &y)using namespace std; const int N = 5010; int n, s, sumt[N], sumc[N], f[N]; int main() { read(n, s); for (int i = 1; i <= n; i++) { int t, c; read(t, c); sumt[i] = sumt[i - 1] + t; sumc[i] = sumc[i - 1] + c; } for (int i = 1; i <= n; i++) { f[i] = 0x3f3f3f3f; for (int j = 0; j < i; j++) { f[i] = min(f[i], f[j] + (sumc[n] - sumc[j]) * s + (sumc[i] - sumc[j]) * sumt[i]); } } cout << f[n]; return 0; }

【斜率优化的dp问题】同上优化
解法二

#include #include #include #include typedef long long ll; #define read(x, y) scanf("%lld%lld", &x, &y)using namespace std; const int N = 300010; ll n, s, sumt[N], sumc[N], f[N]; int hh, tt, q[N]; ll X(int i) { return sumc[i]; }ll Y(int i) { return f[i]; }double slope(int i1, int i2) { return (double) (Y(i1) - Y(i2)) / (double) (X(i1) - X(i2)); }int main() { read(n, s); for (int i = 1; i <= n; i++) { ll t, c; read(t, c); sumt[i] = sumt[i - 1] + t; sumc[i] = sumc[i - 1] + c; } for (int i = 1; i <= n; i++) { while (hh < tt && slope(q[hh], q[hh + 1]) < s + sumt[i]) { hh++; } f[i] = f[q[hh]] + (sumc[n] - sumc[q[hh]]) * s + (sumc[i] - sumc[q[hh]]) * sumt[i]; while (hh < tt && slope(i, q[tt - 1]) <= slope(q[tt], q[tt - 1])) { tt--; } q[++tt] = i; } cout << f[n]; return 0; }