关于算法:斜率优化的dp问题

34次阅读

共计 4413 个字符,预计需要花费 12 分钟才能阅读完成。

洛谷 P3195 [HNOI2008] 玩具装箱

题目介绍

链接:https://www.luogu.com.cn/prob…

解题报告

解法一(TLE)

看到题首先写出暴力版本 dp

#include <iostream>
#include <algorithm>

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 <iostream>
#include <algorithm>

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 <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

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 <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

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 <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

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;
}

同上优化

解法二

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

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;
}

正文完
 0