Beta Round #67-D: Big Maximum Sum

問題概要

長さ5000(=L)以下の数列がN(<50)個与えられる。その数列をM(<250000)個連結させて(重複あり)新しい数列を作り、新しい数列の連続する最大の部分和を求める問題。

解法

「珠玉のプログラミング」とかにも載ってる有名な最大部分和を線形時間で求める問題の応用。前から数えたときの最大部分和、全体の和、後ろから数えたときの最大部分和、単なる最大部分和、を各数列に対して前処理で計算しておけば、動的計画法っぽく解ける。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long int64;

int64 INF = 1LL<<62;

int as[59][5009];
int64 ls[59];
int64 ds[52][4];
int N, M;
vector<int> ms;

void init(){
	for(int i=0; i<N; i++){
		for(int j=0; j<ls[i]; j++){
			ds[i][1] += as[i][j];
		}
		int64 tmp = 0;
		for(int j=0; j<ls[i]; j++){
			tmp += as[i][j];
			ds[i][0] = max(ds[i][0], tmp);
		}
		tmp = 0;
		for(int j=ls[i]-1; j>=0; j--){
			tmp += as[i][j];
			ds[i][2] = max(ds[i][2], tmp);
		}
		int64 cont = 0;
		for(int j=0; j<ls[i]; j++){
			cont = max(0LL, cont + as[i][j]);
			ds[i][3] = max(ds[i][3], cont);
		}
	}

}

int64 solve(){
	int64 ans = 0, cont=0, cur=0;
	init();

	for(int i=0; i<ms.size(); i++){
		int idx = ms[i];
		ans = max(ans, cont + ds[idx][0]);
		ans = max(ans, ds[idx][3]);
		cont = max(0LL, cont + ds[idx][1]);
		cont = max(cont, ds[idx][2]);
		//cout << "  ***  " << cont << endl;
	}

	if(ans==0){
		sort(ms.begin(), ms.end());
		ms.erase(unique(ms.begin(), ms.end()), ms.end());
		ans = -INF;
		for(int i=0; i<ms.size(); i++){
			int id = ms[i];
			for(int j=0; j<ls[id]; j++){
				ans = max(ans, (int64)as[id][j]);
			}
		}
		return ans;
	}
	return ans;
}

int main(){
	scanf("%d%d",&N,&M);
	for(int i=0; i<N; i++){
		int L;
		scanf("%d",&L);
		ls[i] = L;
		for(int j=0; j<L; j++){
			scanf("%d", as[i] + j);
		}
	}
	for(int i=0; i<M; i++){
		int x;
		scanf("%d",&x);
		ms.push_back(x-1);
	}
	cout << solve() << endl;
	return 0;
}