CFR 467 C. George and Job ( DP )

Problem - C - Codeforces
題意：
給一個序列，取 K 段相互不重疊的長度為 M 的連續區間，求可能最大權值和。
解法：
dp[ i ][ j ] : 已考慮序列中前 i 個值，已取 j 塊連續區間，此時的最大權值和。

int N, M, K;
vi A;

void init(){
	cin >> N >> M >> K;
	A = vi( N );
	for( int i = 0; i < N; ++i )
		cin >> A[ i ];
}

vl pA;
vvl dp;

void preprocess(){
	pA = vl( N + 1 );
	for( int i = 0; i < N; ++i )
		pA[ i + 1 ] = pA[ i ] + A[ i ];
	dp = vvl( N + 1, vl( K + 1 ) );
	for( int i = 0; i < N; ++i )
		for( int k = 0; k <= K; ++k ){
			upmax( dp[ i + 1 ][ k ], dp[ i ][ k ] );
			if( i + M <= N and k + 1 <= K )
				upmax( dp[ i + M ][ k + 1 ], dp[ i ][ k ] + pA[ i + M ] - pA[ i ] );
		}
}

void solve(){
	cout << dp[ N ][ K ] << endl;
}