不考虑具体怎么拿,只考虑每层拿到几个。
用f[i][j]存第i层拿了j个时的最大价值,求的方式是去掉一段连续的值之后剩余的最大价值。
要说的代码里都有注释了。
#include<bits/stdc++.h> #define fi first #define se second #define pb(i) push_back(i) #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=b;i>=a;i--) #define mem(a,b) memset(a,b,sizeof(a)) #define VI vector<int> #define VLL vector<ll> #define MPII map<pair<int,int>,int> #define VPII vector<pair<int,int>> #define mp make_pair #define PQI priority_queue<int> #define lowbit(x) x&-x #define debug(a) cout<<#a<<'='<<a<<'\n' using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1e6+10; const int INF = 0x3f3f3f3f; const int inf = - INF; const int mod = 1e9+7; const double pi = acos(-1.0); const double eps=1e-5; vector<int> v[10005]; ll f[105][10005];//第i层拿j个的最大值 ll d[105][10005];//到第i层拿了j个 ll sum[105][100005];//每一层的前缀和,用于求f int main(){ int n, m, x, c; ll ans = 0; scanf("%d%d", &n, &m); for (int x, i = 1; i <= n; i++) { scanf("%d", &x); for (int t,j = 0; j < x; j++) { scanf("%d", &t); if(j > 0)sum[i][j] = sum[i][j - 1] + t; else sum[i][j] = t; v[i].push_back(t); } } for (int i = 1; i <= n; i++) { int sz = v[i].size(); for (int j = 0; j <= min(m, sz); j++) { int t = v[i].size() - j; //k 从第k个开始挖 //t 挖几个 //printf("t = %d\n",t); ll& tmp = sum[i][v[i].size()-1]; if(t > 0) { for (int k = 0; k + t - 1 < v[i].size();k++) { if (k > 0) f[i][j] = max(f[i][j], tmp - (sum[i][k + t - 1] - sum[i][k - 1])); else f[i][j] = max(f[i][j], tmp - sum[i][k + t - 1]); } } else f[i][j] = tmp; //printf("sum[%d] = %lld ,f[%d][%d] = %lld\n",i,sum[i][v[i].size()-1],i,j,f[i][j]); } } for (int i = 1; i <= n; i++) { //int sz = v[i].size(); for (int j = 0; j <= m; j++) { for (int k = 0; k <= j; k++) { d[i][j] = max(d[i - 1][k] + f[i][j - k], d[i][j]); //printf("d[%d][%d] = %lld\n", i, j, d[i][j]); } } } printf("%lld\n",d[n][m]); return 0; }