Codeforces Round #186 (Div. 2) D. Ilya and Roads

,

実質的に重複するクエリを全てまとめてしまってからdpをする。 私にとって、すごく難しいということもないが、決して自明ではない問題。

練習にはこれぐらいの難易度がちょうどよいように思うので、次に練習会でdiv2を使うときはD問題から解きたい。

D. Ilya and Roads

問題

$1 \dots n$($n \le 300$)上の重み付き区間$([l,r],c)$が$m$個($m \le 10^5$)与えられる。 この中から区間をいくつか選んで、選んだ区間のいづれかに覆われている面積が$k$以上になるようにしたい。 このように選ぶとき、選んだ区間の重みの総和の最小値はいくらか。

解法

愚直にdpをするとすると、dp[どこまでみたか][どれだけ覆ったか] = 重みという表を更新していくことになる。 ただし更新は、与えられた区間を右端が小さい順に、その区間を用いて新しく覆う区間の左端を全て試して更新する。 つまり${\rm dp}_{r,k} = {\rm min}(\{ {\rm dp}_{r-1,k} \} + \{ {\rm dp}_{i,k-(r-i)} + c \mid l \le i \lt r \})$のようにする。 これは$O(mnk)$であり、間に合わない。

計算量を落とすため、区間$[l,r)$を覆えるようなあるひとつの区間で重みが最小のものの重み、を全て事前に計算しておけばよい。 そうすると、点$r$を右端に持つような区間が高々ひとつだけであるかのように、表を更新できる。これは$O(n^2k)$となり通る。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
constexpr ll inf = 1ll<<60;
int main() {
    int n, m, k; cin >> n >> m >> k;
    ++ n; // extention of road is ok
    vector<vector<ll> > a(n+1, vector<ll>(n+1, inf)); // a[l][r] = c
    repeat (i,m) {
        int l, r; ll c; cin >> l >> r >> c;
        ++ r;
        a[l][r] = min(a[l][r], c);
    }
    repeat (r,n+1) {
        repeat_from (l,1,r) {
            a[l][r] = min(a[l][r], a[l-1][r]);
        }
    }
    vector<vector<ll> > dp(n+1, vector<ll>(k+1, inf)); // dp[r][k] = c
    dp[0][0] = 0;
    repeat_from (r,1,n+1) {
        dp[r] = dp[r-1];
        repeat (l,r) {
            repeat (i,k+1) {
                int j = min(k, i + r-l);
                dp[r][j] = min(dp[r][j], dp[l][i] + a[l][r]);
            }
        }
    }
    cout << (dp[n][k] == inf ? -1 : dp[n][k]) << endl;
    return 0;
}