AGC036D 题解

· · 题解

跟现有题解的推法不太一样。这确实是道非常有 AtCoder 风格的题。

首先看到这种一眼没有多项式做法的题，考虑找性质简化问题。

我们注意到有 n - 1 条 i \to i + 1 的边是永远不会被删去的，考虑以此为突破口，观察与其方向相同的负边的性质。

Key observation：如果我们确定了一条从 i 到 j 的负边必须保留，那么对于 i' \le i，j' \ge j，负边 i' \to j' 在最优解中也必须保留。

证明：考虑证明加入这条边后不影响合法性，如果保留边 i' \to j' 之后出现了负环，那么把这个环中所有走过 i'\to j' 的部分都替换为先用 0 边从 i' 走到 i，再走边 i \to j，然后从 j 用 0 边走到 j'，就会得到一个不经过边 i' \to j' 的负环，说明加入这条边之前也有负环，矛盾了。

既然不影响合法性，所有边权值还都 >0，那加入这条边显然会得到一个更优的解。\Box

所以，最终答案的负边一定连成如下形式：

其中线段表示序列上的一个个区间，区间内部不连边，圆点表示一些孤立点。所有非孤立点向在它后面与其不同区间的非孤立点都有连边。

进一步观察可以发现，孤立点是不存在的，因为将孤立点并入其旁边的区间肯定不劣，这个操作不会影响正边怎么连。

于是在最优解中，原序列可以被划分为 k 个区间 [l_i,r_i]，满足 l_i = r_{i - 1} + 1,l_1 = 1,r_k = n。所有起点终点在同一个区间内的负边都要删掉。而此时能保留的正边 i \to j 必须满足 i 与 j 在同一个区间或者 j 所在区间与 i 所在区间中间没有夹着其它区间。其余的正边都要删掉。

问题转化到这里就很好做了。设 dp_{i,j} 表示考虑到第 i 位，最后一个区间是 [j,i] 的最小代价。 dp_{i,j} 可以从 dp_{j - 1,k} 转移过来，转移时加的代价可以通过二维前缀和快速预处理。总时间复杂度为 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5;
typedef long long ll;
template<typename T> inline bool ckmin(T &x,const T &y) { return (x > y) && (x = y,true);}
int n;
int B[N][N],A[N][N]; // A+,B-
ll dp[N][N];
ll sa[N][N],sb[N][N];
inline ll Query(ll s[N][N],int l1,int r1,int l2,int r2) {
    if(l1 == 0 && l2 == 0) return s[r1][r2];
    if(l1 == 0) return s[r1][r2] - s[r1][l2 - 1];
    if(l2 == 0) return s[r1][r2] - s[l1 - 1][r2];
    return s[r1][r2] - s[l1 - 1][r2] - s[r1][l2 - 1] + s[l1 - 1][l2 - 1];
} 
int main() {
    cin >> n;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j < i;j++) cin >> A[j][i];
        for(int j = i + 1;j <= n;j++) cin >> B[i][j];
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            sa[i][j] = sa[i][j - 1] + sa[i - 1][j] - sa[i - 1][j - 1] + A[i][j],
            sb[i][j] = sb[i][j - 1] + sb[i - 1][j] - sb[i - 1][j - 1] + B[i][j];
    memset(dp,0x3f,sizeof dp);
    ll ans = 1e18;
    dp[0][0] = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            for(int k = 0;k < j;k++)
                ckmin(dp[j][i],dp[k][j - 1] + Query(sb,j,i,j,i) - Query(sa,j,i,j,i) - Query(sa,k,j - 1,j,i));
    for(int i = 1;i <= n;i++) ckmin(ans,dp[i][n]);
    ans += sa[n][n];
    cout << ans << endl;
    return 0;
}