https://atcoder.jp/contests/abc195/tasks/abc195_d
前提知識
解説
https://atcoder.jp/contests/abc195/submissions/20908448
この解法は非想定解です。
想定解は貪欲法であるが、貪欲法を確信的に行うのはやや難しい。
自分は、アルゴリズムの力で何とかなる場合はそちらを採用している。
まずは1クエリ単体で解法を考えてみよう。
パッと見た感じ、マッチング問題のように見える。
マッチング問題といえばフローであるが、最小費用流を使えば問題は解けそうだ。
最小費用流について細かな説明はしないので、他で学習してきてほしい。
今回の問題は各クエリ毎に独立して、最小費用流を使って解ける。
フロー構成
最小費用流だが、最大値を求める問題であるので、
「費用はMAX-コストとして、MAX*最大流量-最小コストが答え」
とやるテクを使う。
フローは以下の通り。表記は(最大流量,コスト)である。
始点→荷物i (1,0)
使える箱jについて、荷物i→箱j (箱jに荷物iが入れられる場合は1でそうでないなら0, MAX-V[i])
箱j→終点 (1,0)
後は、フローを流せばいい。
int N, M, Q, W[50], V[50], X[50]; int L, R; //--------------------------------------------------------------------------------------------------- int solve() { atcoder::mcf_graph<int, ll> mcf(N + M + 2); int st = N + M; int gl = st + 1; int MAX = 1010101; rep(i, 0, N) mcf.add_edge(st, i, 1, 0); rep(i, 0, N) rep(j, 0, M) { if (L - 1 <= j && j <= R - 1) continue; mcf.add_edge(i, N + j, (W[i] <= X[j]), MAX - V[i]); } rep(j, 0, M) mcf.add_edge(N + j, gl, 1, 0); int flow; ll cost; tie(flow, cost) = mcf.flow(st, gl); return 1LL * MAX * flow - cost; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> Q; rep(i, 0, N) cin >> W[i] >> V[i]; rep(i, 0, M) cin >> X[i]; rep(_, 0, Q) { cin >> L >> R; cout << solve() << endl; } }