問題概要
https://atcoder.jp/contests/typical-algorithm/tasks/typical_algorithm_b/editorial
この問題の各区間に重みがあるとしたとき、その得られる重みの最大を求めます。なお、上記リンクの問題は閉区間の[L,R]となっていますが、この記事では「R+=1」をすることによる半開区間の[L,R)として説明します(dpの遷移的に[L,R]だと、ある区間の仕事が終わったその日から新しい仕事を始められてしまうので、半開区間だとそれを防げる)。
解法
- LとRをまとめて座標圧縮する(DP配列のサイズ的に座標圧縮が必要)
- 座圧後の状態でグラフを作成する
-> 各頂点について、今がi番目の頂点としたときにi+1番目の頂点に重み0の辺を張る
-> 各区間のLからRに対して、入力で渡された重みの辺を張る - 構成されたグラフはDAGなのでDPができる。dp[i]=i番目の頂点まで見たときの得られた重みのmax
という流れで解くことができます。座標圧縮をする関係上、計算量にO(logN)がついて、O(NlogN)になります。DP自体はO(N)です。
図にするとこんな感じになります。上が入力時の区間で、下が座圧して辺を追加したときのグラフです。コードを実装してみるとこんな感じになります。
#include <bits/stdc++.h>
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define chmax(x,y) x = max(x,y);
using ll = long long;
using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using vvvvl = vv<vvl>;
using P = pair<ll, ll>;
//------------------------------------------
template<typename T = ll>
struct CC {//snukeさんの座標圧縮
bool initialized;
vector<T> xs;
CC() : initialized(false) {}
void add(T x) { xs.push_back(x); }
void init() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
initialized = true;
}
ll operator()(T x) {
if (!initialized) init();
return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
}
T operator[](ll i) {
if (!initialized) init();
return xs[i];
}
ll size() {
if (!initialized) init();
return xs.size();
}
};
int main() {
ll n;
cin >> n;
CC cc;//座標圧縮用
//[l,r)の区間の重みがc
vl l(n), r(n), c(n);
rep(i, n)cin >> l[i] >> r[i] >> c[i];
rep(i, n) {//座標圧縮用のデータに追加する
cc.add(l[i]);
cc.add(r[i]);
}
rep(i, n) {//座圧後の番号に更新する
l[i] = cc(l[i]);
r[i] = cc(r[i]);
}
ll sz = cc.size();
vv<P>to(sz);//各区間のlとrを頂点として見た時に、各頂点から生えている辺の(行先,重み)を持つ
rep(i, n) {//各区間のLから生やす
to[l[i]].emplace_back(r[i], c[i]);
}
rep(i, sz)to[i].emplace_back(i + 1, 0);//すぐ右の頂点に重み0を生やす、これによって「今見てる区間を採用しない」のような遷移ができる
vl dp(sz + 1, 0);//dp[i]=i番目の頂点まで見たときのmax。先頭に番兵を入れている
rep(i, sz) {//配るDP
for (auto [t, c] : to[i]) {//辺が生えてる行先に配る
chmax(dp[t], dp[i] + c);
}
}
cout << dp[sz] << endl;
}
重み付き区間スケジューリング問題が調べた感じどこのサイトにもないので、重み無しの問題で使用したところACできました。R++をして半開区間にしています(サンプルが弱いらしいのでミスがあるかもしれません)。
https://atcoder.jp/contests/typical-algorithm/submissions/59664175
重みがmを超えないように区間を選んだときに、最大で何個区間を選べるか？という問題だとしてもDP配列に現在の重みを乗せればいけそうですね(TLEする制約が来たらどうするのかは知りません())
ちなみにk個区間が被るのを許すという問題設定では最小費用流で解けるらしいです(蟻本より)。私には最小費用流を理解できていないので解けません。
終わりに
重み付き区間スケジューリング問題の解法が気になって調べたのに誰も記事にしてなかったので書きました。解法をわかりやすく教えてくださったsnukeさんに感謝します(snukeさんから学んだことを記事にしただけなので、このアルゴリズムは正しいという謎の予防線)。
https://www.youtube.com/live/a723sprlaVk?si=poEvfNJFQOxWGnHr&t=11532