题解：P6203 [USACO07CHN] The Bovine Accordion and Banjo Orchestra G

yaochenchen · 2026-04-24 09:32:09 · 题解

[USACO07CHN] The Bovine Accordion and Banjo Orchestra G

更好的阅读体验

题意：给定两个数组 A 和 B，每匹配一次产生贡献 A_i \times B_j，未匹配的连续段损失 (\sum A)^2，匹配不可以产生“交叉”，最大化总贡献。

40pts 我会 DP！

状态：f_{i,j} 表示强制配对 (i,j)，考虑前 i 个手风琴手和前 j 个班卓琴手的最优净收益。
记前缀和 SA_i = \sum_{x=1}^i A_x，SB_j = \sum_{y=1}^j B_y。

转移（从上一对 (k,l)，0\le k<i,\;0\le l<j）：

边界：f_{i,0}=-(SA_i)^2，f_{0,j}=-(SB_j)^2。

答案：

时间复杂度 O(n^4)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[1005], b[1005], sa[1005], sb[1005];
int dp[1005][1005];

int suma(int l, int r) {
    if (l > r) return 0;
    return (sa[r] - sa[l-1]) * (sa[r] - sa[l-1]);
}
int sumb(int l, int r) {
    if (l > r) return 0;
    return (sb[r] - sb[l-1]) * (sb[r] - sb[l-1]);
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sa[i] = sa[i-1] + a[i];
        dp[i][0] = -sa[i] * sa[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        sb[i] = sb[i-1] + b[i];
        dp[0][i] = -sb[i] * sb[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = a[i] * b[j] - suma(1, i-1) - sumb(1, j-1);
            for (int k = 1; k < i; k++) {
                for (int l = 1; l < j; l++) {
                    dp[i][j] = max(dp[i][j], a[i]*b[j] + dp[k][l] - suma(k+1, i-1) - sumb(l+1, j-1));
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max(ans, dp[i][j] - suma(i+1, n) - sumb(j+1, n));
        }
    }
    cout << ans;
    return 0;
}

56pts 我会观察性质！

引理：最优解一定使相邻两对 (k,l) 与 (i,j) 满足 k=i-1 或 l=j-1。
证明提要：若中间有空余，可在中间增加一对匹配，此时损失由于 x^2+y^2 \le (x+y)^2 使花费不增，且收益还增大了。

简化转移（仅需考虑两种紧邻情况）：

1. 上一匹配在 A 侧紧邻（k=i-1，0\le l<j）：

   f_{i,j} = \max_{0\le l<j}\Bigl\{ f_{i-1,l} + A_iB_j - \bigl(SB_{j-1}-SB_l\bigr)^2 \Bigr\}.

2. 上一匹配在 B 侧紧邻（l=j-1，0\le k<i）：

   f_{i,j} = \max_{0\le k<i}\Bigl\{ f_{k,j-1} + A_iB_j - \bigl(SA_{i-1}-SA_k\bigr)^2 \Bigr\}.

其它转移可由引理舍去。计算时取两种情况的最大值。

时间复杂度 O(n^3)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[1005], b[1005], sa[1005], sb[1005];
int dp[1005][1005];

int suma(int l, int r) {
    if (l > r) return 0;
    return (sa[r] - sa[l-1]) * (sa[r] - sa[l-1]);
}
int sumb(int l, int r) {
    if (l > r) return 0;
    return (sb[r] - sb[l-1]) * (sb[r] - sb[l-1]);
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sa[i] = sa[i-1] + a[i];
        dp[i][0] = -sa[i] * sa[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        sb[i] = sb[i-1] + b[i];
        dp[0][i] = -sb[i] * sb[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = a[i] * b[j] - suma(1, i-1) - sumb(1, j-1);
            if (i > 1) {
                for (int l = 1; l < j; l++) {
                    dp[i][j] = max(dp[i][j], a[i]*b[j] + dp[i-1][l] - sumb(l+1, j-1));
                }
            }
            if (j > 1) {
                for (int k = 1; k < i; k++) {
                    dp[i][j] = max(dp[i][j], a[i]*b[j] + dp[k][j-1] - suma(k+1, i-1));
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max(ans, dp[i][j] - suma(i+1, n) - sumb(j+1, n));
        }
    }
    cout << ans;
    return 0;
}

100pts 我会斜率优化！

上凸包

将转移中的平方项展开：

对于固定的 i，记 X(l) = SB_l，Y(l) = f_{i-1,l} - SB_l^2，则我们需要对当前 j 最大化：

（-SB_{j-1}^2 和 A_iB_j 为常数项）。

现在问题转化为：给定平面上若干个点 (X(l), Y(l))（l = 0,1,\dots,j-1），查询斜率为 k = 2\,SB_{j-1} 的直线 y = kx + b 在点集上的最大截距 b（即最大化 Y - kX）所对应的点。
对于求最大值，维护点集的上凸包（上凸壳），斜率单调递增。

完整代码请见：博客链接。

下凸包

目前题解区的两位 dalao 都是使用下凸包的，对原式取负：

展开后可得 Y'(l) = SB_l^2 - f_{i-1,l}，X'(l)=SB_l，查询斜率 k' = 2\,SB_{j-1}，目标变为求 \min\{ Y'(l) - k' X'(l) \}。此时维护下凸包（斜率递增），查询时斜率同样单调递增。

完整代码请见：博客链接。