codeforce problem 148 E

题意：n排花盆，我们可选择m个，每排第一个数字为每排个数，然后给出每个花盆的价值，我们只能从左边或者右边取

思路：bag[i][j]表示第i行取j个花盆的最大价值，那么每行我们可得到取1个，2个。。。。的最大价值，相当于体积为j,价值为bag[i][j],

　　　总容量为m个，这就有点像是背包了，dp[i][j]表示前i行取j个最大价值，不同的是这得一行一行取

#include<bits/stdc++.h>
using  namespace std;

int dp[102][10005];
int bag[102][10005];
int t[103];
int a[102][10005];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
        for(int j=1;j<=t[i];j++){
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i][j-1];
        }
    }
    //bag[i][j]表示第i行去除j个价值最大
    for(int i=1;i<=n;i++){
        for(int j=1;j<=t[i];j++){
            for(int k=0;k<=j;k++){
                bag[i][j]=max(bag[i][j],a[i][k]+a[i][t[i]]-a[i][t[i]-(j-k)]);
            }
        }
    }

    for(int  i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<=t[i]&&k<=j;k++)//对于这一行的j容量，取当前为k体积的价值//
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+bag[i][k]);
        }
    }
    cout<<dp[n][m]<<endl;
}