Codeforces #892 : Div2 E. Maximum Monogonosity

E問題を妙にさっくり解いている。
https://codeforces.com/contest/1859/problem/E

問題

N要素の2つの整数列A,Bが与えられる。
区間[L,R]のコストを、|A[L]-B[R]|+|A[R]-B[L]|とする。

整数Kが与えられるので、N要素のうち合計の長さがKとなるようにいくつかの重ならない区間を選び、コストを最大化せよ。

解法

求めるのはコストの最大化なので、区間に入る際にA[L]とB[L]を±どちらに取るか4通り総当たりしながらDPしていけばよい。
区間を抜けるとき、A[R]とB[R]の加算減算はB[L]及びA[L]と逆となるように取る。

int T,N,K;
int A[3030],B[3030];
ll fromin[3030][2][2];
ll fromout[3030];
ll toin[3030][2][2];
ll toout[3030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		
		FOR(i,N+1) {
			FOR(x,2) FOR(y,2) fromin[i][x][y]=-1LL<<60;
			fromout[i]=-1LL<<60;
		}
		fromout[0]=0;
		FOR(x,N) {
			int a=A[x],b=B[x];
			FOR(i,N+1) {
				FOR(j,2) FOR(k,2) toin[i][j][k]=-1LL<<60;
				toout[i]=-1LL<<60;
			}
			
			FOR(i,N+1) {
				//out->in->out
				toout[i+1]=max(toout[i+1],fromout[i]+abs(b-a)+abs(b-a));
				//out->in
				toin[i+1][0][0]=max(toin[i+1][0][0],fromout[i]+b-a);
				toin[i+1][1][0]=max(toin[i+1][1][0],fromout[i]-b-a);
				toin[i+1][0][1]=max(toin[i+1][0][1],fromout[i]+b+a);
				toin[i+1][1][1]=max(toin[i+1][1][1],fromout[i]-b+a);
				//out->out
				toout[i]=max(toout[i],fromout[i]);
				//in->in
				FOR(j,2) FOR(k,2) toin[i+1][j][k]=max(toin[i+1][j][k],fromin[i][j][k]);
				//in->out
				toout[i+1]=max(toout[i+1],fromin[i][0][0]-a+b);
				toout[i+1]=max(toout[i+1],fromin[i][1][0]+a+b);
				toout[i+1]=max(toout[i+1],fromin[i][0][1]-a-b);
				toout[i+1]=max(toout[i+1],fromin[i][1][1]+a-b);
			}
			
			swap(fromin,toin);
			swap(fromout,toout);
		}
		cout<<fromout[K]<<endl;
		
	}
}

まとめ

絶対値の最大化は4通り試すテクがよく使えるね。