Rockethon 2015 : E2. Subarray Cuts

Dは解けたと思ったらEは歯が立たなかった。
http://codeforces.com/contest/513/problem/E2

問題

N要素の数列A[i]がある。
ここから連続した部分列で互いに重複しないものをK個とる。
(使用しない要素があっても良い)

各部分列を頭から順にS[j]とする。
|S[0]-S[1]| + |S[1]-S[2]| + ... + |S[K-2]-S[K-1]|
の最大値を求めよ。

解法

自力で解けなかったのでEditorialを参考にした。

絶対値を考えるのは大変なので、
max(±(S[0]-S[1]) ± (S[1]-S[2]) ± ... ± (S[K-2]-S[K-1]))
を求めると考えればよい。

2つの関数F(i,j,c1,c2)とG(i,j,c1,c2)を考える。
F(i,j,c1,c2)はA[i]～A[N-1]から、S[j]～S[K-1]を選んだ時の最大値を返す関数である。
G(i,j,c1,c2)は同様にA[i]～A[N-1]から、S[j]～S[K-1]を選んだ時の最大値を返す関数であるが、A[i-1]がS[j]に含まれており、A[i]をS[j]に含めることもできる。
c1,c2はプラスかマイナスいずれかの符号が入る。

S[0]及びS[K-1]以外の場合、A[i]がS[j]に含まれた場合、S[j]は最終的な値に±(S[j-1]-S[j])±(S[j]-S[j+1])だけ貢献するので、A[i]は±(-A[i])±(A[i])の分貢献する。
このことより以下の式が成り立つ。

• F(i,j,c1,c2) = max(f(i+1,j,c1,c2), c1(-A[i])c2(A[i]) + G(i+1, j, c1, c2))
• G(i,j,c1,c2) = max(f(i,j+1,c2,+), f(i,j+1, c2, -), c1(-A[i])c2(A[i]) + g(i+1, j, c1, c2))

前者は、A[i]をS[j]に含めないパターンと、含めるパターンのうち大きい方を取ることを意味する。
後者は、A[i]を新規にS[j+1]に含め、その際符号をプラスマイナス両方試すパターンと、A[i]を継続してS[j]に含めるパターンのうち最大値を取ることを意味する。

int N,K;
ll A[50000];

ll F[30300][201][2][2];
ll G[30300][201][2][2];

ll getF(int i,int j,int c1,int c2);
ll getG(int i,int j,int c1,int c2) {
	ll& ret=G[i][j][c1==1][c2==1];
	if(ret!=-1LL<<45) return ret;
	if(i==N) return ret = (j==K-1)?0:-1LL<<40;
	
	ll tmp=0;
	if(j!=0) tmp += -c1*A[i];
	if(j!=K-1) tmp += c2*A[i];
	return ret=max(max(getF(i,j+1,c2,1),getF(i,j+1,c2,-1)), tmp+getG(i+1,j,c1,c2));
}

ll getF(int i,int j,int c1,int c2) {
	ll& ret=F[i][j][c1==1][c2==1];
	if(ret!=-1LL<<45) return ret;
	if(j>K) return -1LL<<40;
	if(j==K) return ret = 0;
	if(i==N) return ret = -1LL<<40;
	
	ll tmp=0;
	if(j!=0) tmp += -c1*A[i];
	if(j!=K-1) tmp += c2*A[i];
	return ret=max(getF(i+1,j,c1,c2), tmp+getG(i+1,j,c1,c2));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	FOR(i,N+10) FOR(j,K+3) F[i][j][0][0]=F[i][j][0][1]=F[i][j][1][0]=F[i][j][1][1]=-1LL<<45;
	memmove(G,F,sizeof(F));
	
	ll ma=-1LL<<40;
	ma=max(ma,getF(0,0,1,1));
	ma=max(ma,getF(0,0,1,-1));
	ma=max(ma,getF(0,0,-1,1));
	ma=max(ma,getF(0,0,-1,-1));
	
	cout<<ma<<endl;
}

まとめ

このメモ化再帰は思いつかんわ…。