Codeforces #681 Div1 D. Sum

なるほど。
https://codeforces.com/contest/1442/problem/D

問題

N個の単調増加な数列が与えられる。
これらの数列のそれぞれprefixを何要素か選び、合計K個を選択したとする。
その値の総和の最大値を求めよ。

解法

数列が単調増加ということは、2個以上の数列について部分的に要素を抜き出すことは考えられない。
よって、部分的に要素を抜き出すのは1つの数列だけであり、それ以外は全体を選ぶか全く選ばないかのどちらかである。

そこで、分割統治の要領で以下を行う。
func(L,R,dp) := 部分的に要素を抜き出すのが、L番目以降R番目未満の数列である場合を考える。
配列dpは、他の数列について全体を選ぶか全く選ばないかのどちらかであるとき、抜き出す要素数ごとの総和の最大値を格納する。

MをLとRの中間とする。

• dp2 := dpに対し、加えてL番目以降M番目未満の数列について全体を選ぶか全く選ばないかのどちらかであるときを考えたケースを追加する
• dp3 := dpに対し、加えてM番目以降R番目未満の数列について全体を選ぶか全く選ばないかのどちらかであるときを考えたケースを追加する

とすると、再帰的にfunc(L,M,dp3)とfunc(M,R,dp2)を処理して行けばよい。

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

ll ret;

void hoge(int L,int R,vector<ll> X) {
	if(L+1==R) {
		int i;
		ll sum=0;
		FOR(i,min(K,T[L])+1) {
			if(i) sum+=A[L][i-1];
			ret=max(ret,sum+X[K-i]);
		}
		return;
	}
	int M=(L+R)/2;
	vector<ll> Y=X,Z=X;
	int i,j;
	for(i=L;i<M;i++) for(j=K;j>=T[i];j--) Y[j]=max(Y[j],Y[j-T[i]]+S[i]);
	for(i=M;i<R;i++) for(j=K;j>=T[i];j--) Z[j]=max(Z[j],Z[j-T[i]]+S[i]);
	hoge(L,M,Z);
	hoge(M,R,Y);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>T[i];
		FOR(j,T[i]) cin>>A[i][min(3000,j)];
		T[i]=min(T[i],3000);
		FOR(j,T[i]) S[i]+=A[i][j];
	}
	
	vector<ll> dp(K+1,-1LL<<60);
	dp[0]=0;
	hoge(0,N,dp);
	
	cout<<ret<<endl;
}

まとめ

この実装テクと、選び方の特性は覚えておこうかな。