斜率DP

BB

此时，一个1000 A+B Problem做不出来的菜鸡选手路过 QAQ

 

Introduction

斜率DP，是一种优化DP的方法，其将DP方程转为平面上直线的形式，后通过最大化（最小化）直线截距的方法找到最优决策点。一般情况下，其通过二元组(x,y)的单调性与直线斜率的单调性，通过维护凸包的方法使DP的复杂度由O(n^2)降至O(n)

 

The Fair Nut and Rectangles - Codeforces 1083E

Description
给定n个矩阵，第i个矩形的坐标是(0,0), (xi,0), (0, yi), (xi, yi)，价值为ai，矩阵间不会嵌套，问如何选择这些矩阵的一个子集，使得子集内的矩阵的并减这些矩阵的总价值的值最大
范围： n <= 10^6
Sample Input

3
4 4 8
1 5 0
5 2 10
4
6 2 4
1 6 2
2 4 3
5 3 8

Sample Output

9
10

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = (int)1e6 + 15;
const ll inf = (ll)9e18;
const int MOD = 998244353;
const double eps = 1e-10;
const double PI = acos(-1);

inline double dcmp(double x) {
    return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}

struct Node {
    int x, y;
    ll w;
    bool operator < (const Node& b) const {
        return x < b.x;
    }
};

Node a[N];
int que[N];
ll f[N];

inline ll calc(int i, int j) {
    return f[j] + 1LL * (a[i].x - a[j].x) * a[i].y - a[i].w;
}

inline double cmp(int i, int j) {
    ll dy = f[i] - f[j];
    int dx = a[i].x - a[j].x;
    return (double)dy / dx;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%lld", &a[i].x, &a[i].y, &a[i].w);
        }
        sort(a + 1, a + 1 + n);

        que[1] = 0;
        for(int i = 1, l = 1, r = 1; i <= n; i++) {
            while(l + 1 <= r && calc(i, que[l]) <= calc(i, que[l + 1])) {
                l++;
            }
            f[i] = calc(i, que[l]);

            while(r >= 2 && cmp(que[r - 1], que[r]) < cmp(que[r], i)) {
                r--;
            }
            l = min(r, l);
            que[++r] = i;
        }

        printf("%lld\n", *max_element(f + 1, f + 1 + n));
    }
}

 

「SDOI2016」征途 - Loj 2035

Description
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v×m×m是一个整数。为了避免精度误差，输出结果时输出v×m×m。
对于 100% 的数据，1≤n≤3000
保证从 S 到 T 的总路程不超过 30000 。
Sample Input

5 2
1 2 5 8 6

Sample Output

36

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = (int)3000 + 15;
const ll inf = (ll)9e18;
const int MOD = 998244353;
const double eps = 1e-10;
const double PI = acos(-1);

struct Point {
    ll x, y;
};
typedef Point Vector;

inline ll cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; }

int a[N];
ll f[N][N], g[N];
int que[N];

inline ll calc(int p, int i, int k) { return f[p][k] - 2LL * g[i] * g[k]; }

inline Vector getVec(int p, int i, int j) {
    ll x1 = g[i], y1 = f[p][i];
    ll x2 = g[j], y2 = f[p][j];
    return Vector{ x1 - x2, y1 - y2 };
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; i++) {
            ;
            g[i] = g[i - 1] + a[i];
            f[1][i] = 2 * g[i] * g[i];
        }

        for (int j = 2; j <= m; j++) {
            int l = 1, r = 0;
            que[++r] = j - 1;
            for (int i = j; i <= n; i++) {
                while (l + 1 <= r && calc(j - 1, i, que[l]) >= calc(j - 1, i, que[l + 1])) {
                    l++;
                }
                f[j][i] = calc(j - 1, i, que[l]) + 2 * g[i] * g[i];
                while (r >= 2 && cross(getVec(j - 1, que[r], que[r - 1]), getVec(j - 1, i, que[r])) < 0) {
                    r--;
                }
                l = min(l, r);
                que[++r] = i;
            }
        }

        ll ans = m * (f[m][n] - g[n] * g[n]) - g[n] * g[n];
        printf("%lld\n", ans);
    }
}