Codeforces #608 Div2 D. Portals

長い問題文は見る気なくすなぁ。
https://codeforces.com/contest/1271/problem/D

問題

K人の兵士がいる軍隊がN個ある城を落としていく。
城iは端から順に落としていく。その際A[i]人以上の兵士が必要で、また城を落とすとB[i]人兵士が補充される。
城を落とした後、以下の選択肢をとれる。

• 落とした城に1人兵士を残す
• 後方の城に向けて道がある場合、道にそって後方の城に兵士を1人残す

落とした後の城は1人以上兵士を残した場合、占拠した状態となる。
全城を落とすような戦略を取る場合、占拠した城の価値の最大値を求めよ。

解法

ある城に兵士を残す場合、できるだけ遅いタイミングで兵士をよこした方がよいので、まず道をたどりいつまでタイミングを遅らせられるか求める。
次に、城を落とす際の余兵力を考える。余兵力がある場合、その分以前の城に兵を回せるので、たどれるうちで価値の最も高いところに回していこう。

int N,M,K;
int A[5050],B[5050],C[5050];
int more[5050];
int chance[5050];
vector<int> E[5050];
vector<int> cand[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		if(K<A[i]) return _P("-1\n");
		more[i]=K-A[i];
		K+=B[i];
		chance[i]=i;
	}
	more[N]=K;
	FOR(i,M) {
		cin>>x>>y;
		chance[y-1]=max(chance[y-1],x-1);
	}
	FOR(i,N) E[chance[i]].push_back(i);
	for(i=N-1;i>=0;i--) {
		more[i]=min(more[i],more[i+1]);
		FORR(e,E[i]) cand[more[i+1]].push_back(C[e]);
	}
	
	int ret=0;
	multiset<int> S;
	for(i=5000;i>=1;i--) {
		FORR(e,cand[i]) S.insert(e);
		if(S.size()) {
			ret+=*S.rbegin();
			S.erase(S.find(*S.rbegin()));
		}
	}
	cout<<ret<<endl;
}

まとめ

城を落とすとき兵力がいるのはともかく、兵力が減らないのは不思議だね。