昨日のICPC国内予選のDですこし雰囲気の似た区間DPが出てるし、日本勢に有利だった。

problem

図のような形の$2$-辺連結グラフが与えられる。辺には重みが付いている。 $2$-辺連結性を保ったまま辺を削除した場合の、最小重みを答えよ。

solution

DP on intervals. $O(N^3)$.

let $\operatorname{dp}_{[l,r)} = (\text{the minimal cost to make } [l,r) \text{ satisfy the condition})$. Compute this. The interval satisfying the condition is generated by some rules:

  • A cycle makes such an interval.
    • $\operatorname{dp}_{[l,r)} \gets w_{1,l} + w_{2,l} + w_{2,l+1} + \dots + w_{2,r-2} + w_{1,r-2}$.
  • An interval can be extended by simply adding a vertex.
    • $\operatorname{dp}_{[l,r)} \gets \operatorname{dp}_{[l,r-1)} + w_{1,r-2} + w_{2,r-3}$ (the left side).
  • Two such intervals can be merged.
    • $\operatorname{dp}_{[l,r)} \gets \operatorname{dp}_{[l,m+1)} + \operatorname{dp}_{[m,r)}$ for some $m$.

The DP table can be reduced to a $1$-ary one, by fixing as $l = 0$. This makes the complexity $O(N^2)$.

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
class BiconnectedDiv1 { public: int minimize(vector<int> w1, vector<int> w2); };

const int inf = 1e9+7;
int BiconnectedDiv1::minimize(vector<int> w1, vector<int> w2) {
    int n = w1.size() + 1;
    vector<int> w2acc(n-1); repeat (i,n-2) w2acc[i+1] = w2acc[i] + w2[i];
    vector<vector<int> > dp(n, vector<int>(n+1, inf)); // [l, r)
    repeat_from (len,3,n+1) repeat (l,n) {
        int r = l + len;
        if (n < r) break;
        dp[l][r] = w1[l] + w2acc[r-2] - w2acc[l] + w1[r-2];
        setmin(dp[l][r], w1[l] + w2[l] + dp[l+1][r]);
        setmin(dp[l][r], dp[l][r-1] + w1[r-2] + w2[r-3]);
        repeat_from (m,l,r) setmin(dp[l][r], dp[l][m+1] + dp[m][r]);
    }
    return dp[0][n];
}