CodeQUEEN 2023 決勝 : E - Good Partition

これも割とすんなりだった。
https://atcoder.jp/contests/codequeen2023-final-open/tasks/codequeen2023_final_e

問題

整数列Aが与えられる。
これらをいくつかの連続部分列に分割した時、そのスコアは各部分列における最大値と最大値の差の総和とする。
スコアの最大値を求めよ。

解法

この問題は以下のように置き換えられる。

• Aの中身を、スコアに加算する・減算する・何もしない、のいずれかから選べる。ただし、Aのprefixにおいて加算と減算の回数の差は1回以下でなければならない。
• また、全体で加算と減算の回数は一致しなければならない。

あとは加算と減算の回数の差をもってDPすればよい。

ll from[4];
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,4) from[i]=-1LL<<60;
	from[0]=0;
	
	cin>>N;
	FOR(i,N) {
		ll to[4]={-1LL<<60,-1LL<<60,-1LL<<60};
		cin>>x;
		FOR(j,3) to[j]=from[j];
		to[1]=max(to[1],from[0]+x);
		to[2]=max(to[2],from[0]-x);
		to[0]=max(to[0],from[1]-x);
		to[0]=max(to[0],from[2]+x);
		swap(from,to);
	}
	cout<<from[0]<<endl;
	
}

まとめ

言い換えに気付くとすんなり。