Codeforces ECR #096 : F. Realistic Gameplay

不参加だった回。
https://codeforces.com/contest/1430/problem/F

問題

N回の敵の襲来を、銃弾をK個保持できるマガジンを持つ銃で撃退していく。
各敵の襲来は、時刻L[i]にA[i]匹でやってきて、時刻R[i]までに全敵を倒さなければならない。

銃弾1個で1匹敵を倒すことができ、その際には時間がかからない。
しかし、マガジンに弾を充填する場合は時間が1かかる。
マガジンの弾の充填は、マガジンにまだ銃弾が残っていても実施可能である。ただし残弾は捨てられ、再利用されない。

全敵を倒す際に必要な最小銃弾数を求めよ。

解法

f(n) := n回目の敵の襲来を倒し、次の敵の襲来までにマガジンの弾を充填した状態での、使用銃弾数の各定量
とする。f(i)→f(j)の遷移では、途中不必要な弾の充填(敵の来襲の合間の充填)をしない場合を考えよう。
そうするとf(N)はO(N^2)で求められる。

int N,K;
int L[2020],R[2020],A[2020];
ll dp[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N+1) dp[i]=1LL<<60;
	dp[0]=0;
	FOR(i,N) cin>>L[i]>>R[i]>>A[i];
	FOR(i,N) {
		ll cur=dp[i];
		ll lef=K;
		for(j=i;j<N;j++) {
			ll fin;
			if(A[j]<=lef) {
				lef-=A[j];
				fin=L[j];
			}
			else {
				ll ene=A[j]-lef;
				ll need=(ene+(K-1))/K;
				if(need>R[j]-L[j]) break;
				fin=L[j]+need;
				lef=(K-ene%K)%K;
			}
			cur+=A[j];
			if(j<N-1&&fin<L[j+1]) {
				dp[j+1]=min(dp[j+1],cur+lef);
			}
			else if(j==N-1) {
				dp[N]=min(dp[N],cur);
			}
		}
	}
	
	if(dp[N]>1LL<<59) cout<<-1<<endl;
	else cout<<dp[N]<<endl;
}

まとめ

これはそこまで難しくなさそうだけど、本番割と正答者少ないな。