Codeforces #666 Div1 C. Monster Invaders

また妙な設定だな。
https://codeforces.com/contest/1396/problem/C

問題

N個のステージからなるゲームを考える。
各ステージ、HP1のザコがA[i]体とHP2のボスがいる。
これらを以下の武器を使い倒していく。

• 時間R1をかけ、1体の敵に1のダメージを与える
• 時間R2をかけ、ステージ内の敵を全滅させる
• 時間R3をかけ、敵を1対倒す

なお、ボスに1つ目の武器を使う場合、ボスは倒せないことになるが、その場合いったん隣のステージに移動しなければならない。（また戻ってきて、いずれかの武器でボスを倒す）
ステージ間の移動は時間Dがかかる。
全ステージの敵を全滅するのにかかる最短時間はいくらか。

解法

各ステージについて、敵を全滅させて先に進む場合と、ボスのHPを1残したまま次に進む場合それぞれの最短時間を求めよう。
後者の場合、さらに次のステージに進む前に、一旦戻ってHPを残したボスを倒してから進もう。

ll N;
ll R[3],D;
ll A[1010101];

ll dp[1010101][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d%d%d",&x,&y,&i,&j,&k);
	N=x;
	R[0]=y;
	R[1]=i;
	R[2]=j;
	D=k;
	FOR(i,N) {
		scanf("%d",&x);
		A[i]=x;
	}
	
	dp[0][0]=0;
	dp[0][1]=1LL<<60;
	ll ret=1LL<<60;
	FOR(i,N) {
		dp[i+1][0]=dp[i+1][1]=1LL<<60;
		
		dp[i+1][0]=min(dp[i+1][0],dp[i][0]+1LL*A[i]*R[0]+R[2]+D);
		dp[i+1][0]=min(dp[i+1][0],dp[i][1]+1LL*A[i]*R[0]+R[2]+3*D);
		dp[i+1][0]=min(dp[i+1][0],dp[i][1]+min((ll)R[1]+R[0],1LL*(A[i]+2)*R[0])+3*D);
		if(i==N-1) ret=min(ret,dp[i][1]+1LL*A[i]*R[0]+R[2]+D);
		dp[i+1][1]=min(dp[i+1][1],dp[i][0]+min((ll)R[1]+R[0],1LL*(A[i]+2)*R[0])+D);
	}
	ret=min(ret,dp[N][0]-D);
	ret=min(ret,dp[N][1]+D);
	cout<<ret<<endl;
	
	
}

まとめ

設定がややこしい割に、余り面白いと感じられない問題だった。