http://codeforces.com/contest/863/problem/F
フローと言われちゃえばねぇ…。
まず配列の各iについてA[i]以上B[i]以下ではならないという条件を求める。B[i] < A[i]ならもちろん-1を返す。
それからはフローで値を求めるのだが、区間N個にN * 2 + j(0 <= j < N)という番号を振り当てると、
N * 2 + jからA[i] <= x <= B[i]を満たすxに辺を張り、xには1流すとコスト1,2流すとコスト3...k流すとコスト2*k+1になるように辺を張る。
そうすると、xにk流れた時コストはk^2になるのであとはこれの最小費用流を求めればよい。
int N, Q; int A[MAX_N], B[MAX_N]; int cnt[MAX_N]; void solve() { cin >> N >> Q; rep(i, 0, N) B[i] = N - 1; while(Q--) { int q, a, b, c; cin >> q >> a >> b >> c; a--; b--; c--; if(q == 1) { for(int i = a; i <= b; i++) MAX(A[i], c); } else { for(int i = a; i <= b; i++) MIN(B[i], c); } } rep(i, 0, N) { if(B[i] < A[i]) { cout << -1 << "\n"; return; } } MCC::init(N * 3 + 1); int t = N * 3; rep(i, 0, N) { MCC::set_d(N * 2 + i, -1); for(int j = A[i]; j <= B[i]; j++) { MCC::add_edge(N * 2 + i, j, inf, 0); MCC::add_edge(j, j + N, 1, cnt[j] * 2 + 1); cnt[j]++; MCC::add_edge(j + N, t, inf, 0); } } MCC::set_d(t, N); cout << MCC::get() << "\n"; }
循環最小費用流(各点について流量を設定できるヤツ)を使ったが、普通に下限設定できる最小費用流ライブラリが欲しいと思った。(こなみ)