https://arc085.contest.atcoder.jp/tasks/arc085_c
maximum closure problemという問題なんですが、集合を2つに分ける+DPでできない場合は疑ったほうがいいです。
さて今回最大化したいのは、
S-min(Σbi+Σci)です。ここでbiは破壊する宝石のうち値が正のものであり、ciは破壊しない宝石のうち値が負のものについて絶対値をとったものです。
Sをsupersource,Tをsupersinkとして、S側にグラフcutが含まれるとき宝石を破壊し、T側に含まれていたら宝石を破壊しないことにします。
そうすると、宝石n*iはiの倍数なので、n*iが破壊されないのにiが破壊されるということはありません。なのでi->n*iにコスト無限の辺を張ります。
あと、i->Tにコストbiの辺を張ることで、もしbiが破壊されるグループに入ってる場合、その分損をしていることを表現します。
同じようにS->iにコストciの辺を張れば完成です。あとはSからTにフローを求めればmin(Σbi+Σci)が求められます。
int N; int A[MAX_N]; void solve() { cin >> N; ll S = 0; rep(i, 1, N + 1) { cin >> A[i]; if(A[i] >= 0) S += A[i]; } int s = N + 1, t = N + 2; MF::init(N + 3); rep(i, 1, N + 1) { for(int j = i * 2; j <= N; j += i) { MF::add_edge(i, j, linf); } } rep(i, 1, N + 1) { if(A[i] >= 0) { MF::add_edge(i, t, A[i]); } else MF::add_edge(s, i, -A[i]); } cout << S - MF::get(s, t) << "\n"; }