Codeforces #745 Div1 : D. Subsequence

また問題文の解釈に手間取るな。
https://codeforces.com/contest/1580/problem/D

問題

各要素の値が異なるn要素の整数列aが与えられる。
aのうちm要素の部分列(a[b[1]],a[b[1]],... a[b[m]])を考えるとき、そのスコアを

とする。
ここでとする。

n要素中m要素を含む部分列のスコアの最大値を求めよ。

解法

dp(L,R,m) := a[L...R]のうちm要素を選んだ時のスコア
とする。DFSの要領で、a[L...R]のうち最小値をa[C]とする。その場合、まずdp(L,C-1,x)とdp(C+1,R,y)を求めたうえで、bの間にCが含まれるようなケースをx,yごとに総当たりしよう。

int N,M;
ll A[4040];
ll F[4040][4040];

vector<ll> dfs(int L,int R) {
	int C=L;
	int i,x,y;
	for(i=L;i<R;i++) if(A[i]<A[C]) C=i;
	vector<ll> X={0,(M-1)*A[C]};
	if(L<C) {
		vector<ll> Y=dfs(L,C);
		vector<ll> Z(X.size()+Y.size()-1,-1LL<<60);
		FOR(x,X.size()) FOR(y,Y.size()) {
			chmax(Z[x+y],X[x]+Y[y]-2*x*y*A[C]);
		}
		X=Z;
	}
	if(C+1<R) {
		vector<ll> Y=dfs(C+1,R);
		vector<ll> Z(X.size()+Y.size()-1,-1LL<<60);
		FOR(x,X.size()) FOR(y,Y.size()) {
			chmax(Z[x+y],X[x]+Y[y]-2*x*y*A[C]);
		}
		X=Z;
	}
	return X;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	auto V=dfs(0,N);
	cout<<V[M]<<endl;
	
}

まとめ

なんか解法ありきで作った問題に見えるな…。