yukicoder : No.1117 数列分割

これ系は何度も見てるしね。
https://yukicoder.me/problems/no/1117

問題

N要素の整数列Aが与えられる。
これらを、要素数1個以上M個以下の数列K個に分割する。
その時、各分割した数列の和の絶対値の総和を取るとき、その最大値を求めよ。

解法

f(n,k) := 元数列のprefix n要素を分割して数列をk個にしたときの、各数列の和の絶対値の総和の最大値
とする。f(0,0)=0から初めてf(N,K)を求めたい。

S[i]をAの先頭i要素のprefixの累積和とする。
f(n,k) = max(f(n-i,k-1)+|S[n]-S[n-i]|) (1≦i≦min(n,M))
となるが、絶対値が邪魔である。なので両パターン計算することにしよう。
f(n,k) = max(f(n-i,k-1)+S[n]-S[n-i], f(n-i,k-1)-S[n]+S[n-i])

これには、f(m,k-1)-S[m]及びf(m,k-1)+S[m]の最大値を区間内で高速に取り出せる必要がある。
Segtreeでも間に合うかもしれないが、割とシビアなTLなのでスライド最大値を使うとよい。

int N,K,M;
int A[3030];
ll S[3030];

ll from[3030],to[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>M;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	FOR(i,N) from[i+1]=-1LL<<60;
	from[0]=0;
	while(K--) {
		FOR(i,N+1) to[i]=-1LL<<60;
		deque<pair<ll,int>> D[2];
		D[0].push_back({from[0],0});
		D[1].push_back({from[0],0});
		for(i=1;i<=N;i++) {
			while(D[0].size() && D[0].front().second+M<i) D[0].pop_front();
			while(D[1].size() && D[1].front().second+M<i) D[1].pop_front();
			to[i]=max(to[i],D[0].front().first+S[i]);
			to[i]=max(to[i],D[1].front().first-S[i]);
			while(D[0].size()&&D[0].back().first<=from[i]-S[i]) D[0].pop_back();
			D[0].push_back({from[i]-S[i],i});
			while(D[1].size()&&D[1].back().first<=from[i]+S[i]) D[1].pop_back();
			D[1].push_back({from[i]+S[i],i});
		}
		swap(from,to);
	}
	cout<<from[N]<<endl;
}

まとめ

スライド最大値は先に気が付いて、絶対値の扱いを後に気が付いた。