なかなか面白い問題。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_h
問題
0~(N+1)番の部屋が順に並んでいる。
1~N番の各部屋には以下の何れかがある。
- プレイヤーのHPをB[i]消費し、カギを1つ手に入れられる。
- カギを1つ消費し、プレイヤーの防御力をB[i]上昇させる道具を手に入れる。
- 攻撃力B[i]のモンスターがいる。プレイヤーのHPを(モンスターの攻撃力)-(プレイヤーの防御力)分消費し、モンスターを倒すことができる。
- なお、プレイヤーの防御力がモンスターの攻撃力を上回ることはない。
モンスターのいる部屋は、一度モンスターを倒さないと通過できない。
一度モンスターを倒した部屋やその他の部屋は自由に行き来できる。
0番の部屋から(N+1)番の部屋に移動するのに必要な最小消費HPを求めよ。
解法
最大では各モンスターの合計攻撃力分だけHPを消費する。
あとはカギと道具を適切に取ることで、消費量を減らすことを考える。
これは最小コストフローで求めることができる。
sourceから各カギ、各カギから各道具、各道具からsinkへと有向辺を張ったグラフを考える。
sourceからカギと道具からsinkは容量1、コスト0の辺を張ればよい。
(なお、カギや道具を取らなくても良いので、sourceからsinkに容量無限の辺も張っておく)
カギxから道具yへは、そのカギと道具を得ることで削減できるHP消費量をコストとした辺を張ればよい。
コストの値は、鍵を取るのに必要なHP消費量B[x]から、カギと道具両方取った後に登場するモンスターの数×B[y]を引いたものである。
このコスト値は小さいほどよく、負の値の方が良い。
template<int NV,class V> class MinCostFlow { public: struct edge { int to, capacity; V cost; int reve;}; vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV]; void add_edge(int x,int y, int cap, V cost) { E[x].push_back((edge){y,cap,cost,(int)E[y].size()}); E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */ } V mincost(int from, int to, int flow) { V res=0; int i,v; ZERO(prev_v); ZERO(prev_e); while(flow>0) { fill(dist, dist+NV, numeric_limits<V>::max()/2); dist[from]=0; priority_queue<pair<V,int> > Q; Q.push(make_pair(0,from)); while(Q.size()) { V d=-Q.top().first; int cur=Q.top().second; Q.pop(); if(dist[cur]!=d) continue; if(d==numeric_limits<V>::max()/2) break; FOR(i,E[cur].size()) { edge &e=E[cur][i]; if(e.capacity>0 && dist[e.to]>d+e.cost) { dist[e.to]=d+e.cost; prev_v[e.to]=cur; prev_e[e.to]=i; Q.push(make_pair(-dist[e.to],e.to)); } } } if(dist[to]==numeric_limits<V>::max()/2) return -1; int lc=flow; for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity); flow -= lc; res += lc*dist[to]; for(v=to;v!=from;v=prev_v[v]) { edge &e=E[prev_v[v]][prev_e[v]]; e.capacity -= lc; E[v][e.reve].capacity += lc; } } return res; } }; MinCostFlow<1002,ll> mcf; int N; ll A[1000],B[1000]; ll M[1000],NK; ll ret; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]>>B[i]; for(i=N-1;i>=0;i--) M[i]=M[i+1]+(A[i]==2); FOR(i,N) { if(A[i]==0) mcf.add_edge(0,10+i,1,0), NK++; if(A[i]==1) mcf.add_edge(10+i,1000,1,0); if(A[i]==2) ret+=B[i]; } FOR(x,N) if(A[x]==0) { FOR(y,N) if(A[y]==1 && B[x]-M[max(x,y)]*B[y]<0) mcf.add_edge(10+x,10+y,1,B[x]-M[max(x,y)]*B[y]); } mcf.add_edge(0,900,NK,0); cout << ret+mcf.mincost(0,1000,NK) << endl; }
まとめ
最小コストフローということに気づいてしまえば、グラフの形もわかりやすいシンプルな問題だね。