Codeforces Round #68 D. Big Maximum Sum

問題概要

小数列がいくつか与えられる。
小数列をいくつかつなげた大数列が、小数列の番号の列により与えられる。

このとき、大数列において連続する項の和の最大値を求めよ。
小数列の数は50以下、それぞれの項数は5000以下、
大数列を作る小数列の番号の列の長さは250000以下である。

解法

数列の連続する項の和の最大値を求めるDPは以下のようにできる。
dp[i]を、i番目までで、連続する項の和の最大値とすると、
dp[i]=max(dp[i-1]+a[i],a[i])


このDPを、両端だけ「小数列の左端から見た連続する項の最大値」、
「小数列の右端から見た連続する項の最大値」にしてやればよい。

ソースコード

int n,m;
ll lmax[50], rmax[50], sum[50], mx[50];
int b[250000];
bool use[50];

void run(){
  scanf("%d%d",&n,&m);

  rep(i,n){
    int len,a[5000];
    scanf("%d",&len);
    rep(j,len)scanf("%d",a+j);

//前処理で、それぞれの小数列において、左端から連続する項の和の最大値
//右端から連続する項の和の最大値を求めておく。
//mx[i]は、小数列において、連続する項の和の最大値であり、
//これは、全体の和の最大の部分が小数列一つに収まってしまっている場合にのみ使う。
    lmax[i]=rmax[i]=mx[i]=-inf;
    ll s=0,t=0,u=0;
    rep(j,len){
      s+=a[j]; t+=a[len-1-j];
      lmax[i]=max(lmax[i],s);
      rmax[i]=max(rmax[i],t);
      u=max((ll)a[j],u+a[j]);
      mx[i]=max(mx[i],u);
    }
    sum[i]=s;
    use[i]=0;
  }
  rep(i,m)scanf("%d",b+i), use[--b[i]]=1;

  ll ans=-inf, s=rmax[b[0]];

  rep(i,n)if(use[i])ans=max(ans,mx[i]);
  ans=max(ans, max(lmax[b[0]],rmax[b[0]]));

  for(int i=1;i<m;i++){
    ans=max(ans,s+lmax[b[i]]); //区間の終了は左端からの最大値
    s=max(rmax[b[i]],s+sum[b[i]]); //区間の開始は右端からの最大値を使う
  }
  cout<<ans<<endl;
}