Codeforces 148E. Porcelain

問題

n個の棚がある。棚から合計m個の品を取りたい。
それぞれの棚は、先頭または末尾からしか品物を取り出すことは出来ない。

それぞれの棚の品物の価値が与えられたとき、
取り出せる価値の合計の最大値はいくつか、求めよ。

制約条件

n≦100, m≦10000
それぞれの棚の品物の数≦100
それぞれの品物の価値≦100

方針

棚ごとに、i個品物を取り出すときの価値の最大値を前計算により求める。
これは、i個のうちj個を先頭から取り出し、i-j個を末尾から取り出すとして、jを全通り試せばいい。

その後、以下のような動的計画法により答えを求める。
dp[i]をi個の品物で得られる価値の最大値とする。
これを、棚ごとに更新していく。

ソースコード

int dp[10001];
int num[100], mx[100][101];

void calc(int *a, int n, int *s){
	int sum[101]={};
	rep(i,n)sum[i+1]=sum[i]+s[i];
	
	for(int i=1;i<=n;i++){
		rep(l,i+1)a[i]=max(a[i], sum[l]+sum[n]-sum[n-i+l]);
	}
}

void run()
{
	int n, m;
	cin>>n>>m;
	rep(i,n){
		int s[100];
		cin>>num[i];
		rep(j,num[i])cin>>s[j];
		calc(mx[i], num[i], s);
	}
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	
	rep(i,n)for(int j=m;j>=0;j--)if(dp[j]>=0){
		rep(k,num[i]+1)if(j+k<=m)dp[j+k]=max(dp[j+k], dp[j]+mx[i][k]);
	}
	cout<<dp[m]<<endl;
}