點擊打開鏈接

題意：

有n排花盆，每排有k個，然后有個人想扔m個花瓶，每個花瓶有個價值val

他只能選擇每一排的最左邊或者最右邊扔

求扔的最大價值

思路： bag[i][j]表示第i排扔j個的最大價值， dp[i][j]表示前i排扔j個的最大價值，背包dp

轉移：dp[i][j] = max(dp[i][j],dp[i-1][j-k]+bag[i][k])  0<=k<=t[i];

代碼：

#include <bits/stdc++.h>using namespace std;const int maxn = 105;int n,m,t[maxn],a[maxn][maxn],bag[maxn][maxn];int dp[maxn][10001];int main(){	cin >> n >> m;	for(int i=1; i<=n; i++){		cin >> t[i];		for(int j=1; j<=t[i]; j++){			cin >> a[i][j];			a[i][j] += a[i][j-1];		}	}	for(int i=1; i<=n; i++)		for(int j=1; j<=t[i]; j++)			for(int k=0; k<=t[i] && k<=j; k++)				bag[i][j] = max(bag[i][j], a[i][j-k] + a[i][t[i]] - a[i][t[i]-k]);	for(int i=1; i<=n; i++)		for(int j=0; j<=m; j++)			for(int k=0; k<=t[i] && k<=j; k++)				dp[i][j] = max(dp[i][j],dp[i-1][j-k]+bag[i][k]);	cout << dp[n][m] << endl;}