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;
}