AtCoder ABC #219 (サイシードプログラミングコンテスト2021) : H - Candles

そういやそんなテクあったな…。
https://atcoder.jp/contests/abc219/tasks/abc219_h

問題

1次元の数直線上にいくつかロウソクがあり、それぞれの位置X[i]と長さA[i]が与えられる。
ロウソクは初期状態で火がついており、時刻1で長さが1減少する。たがし、長さが0になったらそれ以上は減らない。

プレイヤーは初期位置で原点におり、速度1で数直線上を左右に移動できる。
また、ロウソクと同じ座標に到達したら、ロウソクの火を消すことで、以後時間経過してもロウソクの長さが減らなくなる。
最適に移動したとき、最終的に残るロウソクの長さの総和を最大化せよ。

解法

プレイヤーの移動の仕方は、未到達のロウソクのうち、左右どちらか最寄のものに移動する、を繰り返すことになる。
よって、DPを行う際、位置に関する情報は、移動済みの区間と、あとプレイヤーが区間の両端どちらにいるか、を持つことになる。

そこでまず、ロウソクの長さが負をとっても良いことを考える。
f(L,R,b) := 区間[L,R]を移動済みで、bがプレイヤーが左右どちらにいるかを表すとき、得られるロウソクの長さの総長の最大値
とする。この時、残ったロウソクがn個なら、時刻1毎に最終的に得られる長さがn減るとみなすと、O(N^2)のDPで解くことができる。

次に、ロウソクの長さが負のものは、そもそも取らない、と考える。
上記アイデアに、「今後あとn個とる」というパラメータを足そう。
g(L,R,b,n) := 区間[L,R]を移動済みで、bがプレイヤーが左右どちらにいるかを表すし、かつ今後あとn個のロウソクを取ることにしたとき、得られるロウソクの長さの総長の最大値
とする。この時、時刻1毎に最終的に得られる長さがn減る。また、区間を伸ばすとき、そのロウソクを取るかとらないか選択できる。
この時g(0,0,false,n)をn=0～Nに対し解き、その最大値を求めればそれが解となる。状態がO(N^3)で遷移はO(1)なので、全体の時間はO(N^3)で済む。

int N;
pair<ll,ll> P[303];
ll dp[303][303][303][2];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	P[N]={0,0};
	N++;
	sort(P,P+N);
	FOR(i,N) if(P[i].second==0) break;
	ll ma=0;
	FOR(x,N+2) FOR(y,N+2) FOR(k,N+2) dp[x][y][k][0]=dp[x][y][k][1]=-1LL<<60;
	FOR(j,N+1) dp[i][i][j][0]=0;
	
	for(int c=N;c>=0;c--) {
		for(int len=0;len<=N;len++) {
			for(int L=0,R=len;R<N;L++,R++) {
				ma=max(ma,dp[L][R][c][0]);
				ma=max(ma,dp[L][R][c][1]);
				if(L>0) {
					//take
					if(c) chmax(dp[L-1][R][c-1][0],dp[L][R][c][0]+P[L-1].second-c*(P[L].first-P[L-1].first));
					chmax(dp[L-1][R][c][0],dp[L][R][c][0]-c*(P[L].first-P[L-1].first));
					
					if(c) chmax(dp[L-1][R][c-1][0],dp[L][R][c][1]+P[L-1].second-c*(P[R].first-P[L-1].first));
					chmax(dp[L-1][R][c][0],dp[L][R][c][1]-c*(P[R].first-P[L-1].first));
				}
				if(R<N-1) {
					if(c) chmax(dp[L][R+1][c-1][1],dp[L][R][c][0]+P[R+1].second-c*(P[R+1].first-P[L].first));
					chmax(dp[L][R+1][c][1],dp[L][R][c][0]-c*(P[R+1].first-P[L].first));
					
					if(c) chmax(dp[L][R+1][c-1][1],dp[L][R][c][1]+P[R+1].second-c*(P[R+1].first-P[R].first));
					chmax(dp[L][R+1][c][1],dp[L][R][c][1]-c*(P[R+1].first-P[R].first));
				}
			}
		}
	}
	
	cout<<ma<<endl;
	
	
}

まとめ

昔1回ぐらいはこれ系のDP見てそう。