P6203 二维斜率优化

· · 题解

题意写的比较清楚。

考虑 DP，令 f_{i,j} 表示前 i 个 A 类奶牛和前 j 个 B 类奶牛匹配的最大收益。

当前两个奶牛前面可以一对匹配的也没有，那么有 f_{i,j}=a_ib_j-(\sum_{x=1}^{i-1}a_x)^2-(\sum_{x=1}^{j-1}b_x)^2，可以从前面已经匹配好的一组转移过来，那么有 f_{i,j} = \max \limits_{k=1} \limits^{i-1} \max\limits_{l=1}^{j-1}f_{k,l}+a_ib_j-(\sum^{i-1}_{x=k+1}a_x)^2-(\sum^{j-1}_{x=l+1}b_x)^2。 由于 i,j 后面可能还有奶牛没有匹配，所以答案是 \max\limits_{i=1}\limits ^n \max\limits_{j=1}\limits^n f_{i,j}-(\sum^n_{x=i+1}a_x)^2-(\sum^n_{x=j+1}b_x)^2。

用前缀和优化一下，可以做到 O(n^4) 的 DP，比较轻松的拿下了 40 分，下面附上代码。

#include <bits/stdc++.h>
const int N = 1005;
typedef long long ll;
using namespace std;
ll a[N], b[N], sa[N], sb[N];
ll f[N][N], ans = LLONG_MIN, n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sa[i] = sa[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i], sb[i] = sb[i - 1] + b[i];
    for (int i = 1; i <= n; i++)
        f[i][0] = -sa[i] * sa[i], f[0][i] = -sb[i] * sb[i];
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) {
            f[i][j] = a[i] * b[j] - sa[i - 1] * sa[i - 1] - sb[j - 1] * sb[j - 1];
            for (int k = 1; k < i; k++) 
                for (int l = 1; l < j; l++) 
                    f[i][j] = max(f[i][j], f[k][l] + a[i] * b[j] - (sa[i - 1] - sa[k]) * (sa[i - 1] - sa[k]) - (sb[j - 1] - sb[l]) * (sb[j - 1] - sb[l]));
            ans = max(ans, f[i][j] - (sa[n] - sa[i]) * (sa[n] - sa[i]) - (sb[n] - sb[j]) * (sb[n] - sb[j]));
        }
    printf("%lld\n", ans);
    return 0;
}

考虑优化，猜想一下转移有没有什么特殊性质。

随机几组数据，记录一下每个点的决策点然后打印。

一批决策点满足 k=i-1，另一批满足 l=j-1。

我们感性理解一下：区间和都是非负的，因为 \forall x,y\geq 0,(x+y)^2\geq x^2+y^2，而且将这个区间断开还有额外的贡献，所以在中间（[k+1,i-1],[l+1,j-1]）添加一组匹配的奶牛不会更坏。那么最后就只剩下 k=i-1 和 l=j-1 这两个决策点连了。

复杂度降为 O(n^3)，卡卡常数应该是能拿到 56 分的，下面附上代码。

#include <bits/stdc++.h>
const int N = 1005;
typedef long long ll;
using namespace std;
ll a[N], b[N], sa[N], sb[N];
ll f[N][N], ans = LLONG_MIN, n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sa[i] = sa[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i], sb[i] = sb[i - 1] + b[i];
    for (int i = 1; i <= n; i++)
        f[i][0] = -sa[i] * sa[i], f[0][i] = -sb[i] * sb[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            f[i][j] = a[i] * b[j] - sa[i - 1] * sa[i - 1] - sb[j - 1] * sb[j - 1];
            if (i > 1) for (int l = 1; l < j; l++)
                    f[i][j] = max(f[i][j], f[i - 1][l] + a[i] * b[j] - (sb[j - 1] - sb[l]) * (sb[j - 1] - sb[l]));
            if (j > 1) for (int k = 1; k < i; k++)
                    f[i][j] = max(f[i][j], f[k][j - 1] + a[i] * b[j] - (sa[i - 1] - sa[k]) * (sa[i - 1] - sa[k]));
            ans = max(ans, f[i][j] - (sa[n] - sa[i]) * (sa[n] - sa[i]) - (sb[n] - sb[j]) * (sb[n] - sb[j]));
        }
    printf("%lld\n", ans);
    return 0;
}

然后这个形式是可以斜率优化的。对两个转移分别开两个队列去斜率优化。不会的看这里。

#include <bits/stdc++.h>
#define X1(k) (sb[k])
#define Y1(k) (sb[k] * sb[k] - f[i - 1][k])
#define X2(k) (sa[k])
#define Y2(k) (sa[k] * sa[k] - f[k][j - 1])
const int N = 1005;
typedef long long ll;
using namespace std;
ll a[N], b[N], q1[N][N], q2[N][N], sa[N], sb[N], h1[N], h2[N], t1[N], t2[N];
ll f[N][N], ans = LLONG_MIN, n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i], sa[i] = sa[i - 1] + a[i];

    for (int i = 1; i <= n; i++)
        cin >> b[i], sb[i] = sb[i - 1] + b[i];

    for (int i = 1; i <= n; i++)
        h1[i] = h2[i] = 1, f[i][0] = -sa[i] * sa[i], f[0][i] = -sb[i] * sb[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = a[i] * b[j] - sa[i - 1] * sa[i - 1] - sb[j - 1] * sb[j - 1];

            while (h1[i] < t1[i] &&
                    (Y1(q1[h1[i] + 1][i]) - Y1(q1[h1[i]][i])) <= (X1(q1[h1[i] + 1][i]) - X1(q1[h1[i]][i])) * 2 * sb[j - 1])
                h1[i]++;

            if (i > 1)
                f[i][j] = max(f[i][j], f[i - 1][q1[h1[i]][i]] + a[i] * b[j] - (sb[j - 1] - sb[q1[h1[i]][i]]) * (sb[j - 1] - sb[q1[h1[i]][i]]));

            while (h1[i] < t1[i] &&
                    (Y1(q1[t1[i]][i]) - Y1(q1[t1[i] - 1][i])) * (X1(j) - X1(q1[t1[i]][i])) >= (Y1(j) - Y1(q1[t1[i]][i])) * (X1(q1[t1[i]][i]) - X1(q1[t1[i] - 1][i])))
                t1[i]--;

            q1[++t1[i]][i] = j;

            while (h2[j] < t2[j] &&
                    (Y2(q2[h2[j] + 1][j]) - Y2(q2[h2[j]][j])) <= (X2(q2[h2[j] + 1][j]) - X2(q2[h2[j]][j])) * 2 * sa[i - 1])
                h2[j]++;

            if (j > 1)
                f[i][j] = max(f[i][j], f[q2[h2[j]][j]][j - 1] + a[i] * b[j] - (sa[i - 1] - sa[q2[h2[j]][j]]) * (sa[i - 1] - sa[q2[h2[j]][j]]));

            while (h2[j] < t2[j] &&
                    (Y2(q2[t2[j]][j]) - Y2(q2[t2[j] - 1][j])) * (X2(i) - X2(q2[t2[j]][j])) >= (Y2(i) - Y2(q2[t2[j]][j])) * (X2(q2[t2[j]][j]) - X2(q2[t2[j] - 1][j])))
                t2[j]--;

            q2[++t2[j]][j] = i;
            ans = max(ans, f[i][j] - (sa[n] - sa[i]) * (sa[n] - sa[i]) - (sb[n] - sb[j]) * (sb[n] - sb[j]));
        }
    }

    printf("%lld\n", ans);
    return 0;
}