NC214520. 爬塔
描述
高川最喜欢的游戏当属 Slay the Spire，这是一款爬塔游戏，你需要从一座塔的底部一直爬到顶部，在爬塔的过程中，塔的每一层都有许多的宝物等你来拿。
高川从塔的左侧开始攀爬，从底部爬到顶部，再从右侧从顶部逐步下到底部。塔总共有 n 层，每一层都有很多宝物从左到右排列。在左侧攀爬时，他只能从每层的最左边按顺序取宝物，在右侧下降时，他只能从每层的最右边按顺序取宝物。每个宝物都有一个价值，他最多拿 m 个宝物，他想知道自己从塔上下来时，最多可以拿的宝物价值和是多少。
输入描述
第一行输入两个正整数和
。表示塔的层数和最多能选的个数。
接下来 n 行,每行先输入一个数字 x。表示这一层宝物的个数。接下来输入 x 个正整数，表示每个宝物的权重 c。
输入保证可挑选的物品大于等于 m 个.
输出描述
输出一个整数表示高川能拿走的最大价值和.
示例1
输入:
2 3 2 3 2 4 1 4 1 5
输出:
10
C++(g++ 7.5.0) 解法, 执行用时: 89ms, 内存消耗: 612K, 提交时间: 2023-02-10 11:08:37
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
const int maxm = 1e4+10;
int a[maxn][maxn];
int x[maxn],ans[maxn][maxn];
int pref[maxn][maxn],suf[maxn][maxn];
int dp[maxm];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
for(int j=1;j<=x[i];j++){
scanf("%d",&a[i][j]);
pref[i][j]=pref[i][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++)
for(int j=x[i];j>=1;j--)
suf[i][j]=suf[i][j+1]+a[i][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=x[i];j++)
for(int k=0;j+k<=x[i];k++)
ans[i][j+k]=max(ans[i][j+k],pref[i][j]+suf[i][x[i]-k+1]);
for(int i=1;i<=n;i++)
for(int j=m;j>0;j--)
for(int k=x[i];k>0;k--)
if(k<=j)
dp[j]=max(dp[j],dp[j-k]+ans[i][k]);
printf("%d\n",dp[m]);
return 0;
}
C++(clang++11) 解法, 执行用时: 33ms, 内存消耗: 2344K, 提交时间: 2020-12-05 18:54:42
#include<bits/stdc++.h>
using namespace std;
int ss,n,m,x[200],a,sum[200][200],d[200][200],dp[110][10010],sx[200];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
sx[i]=sx[i-1]+x[i];
for(int j=1;j<=x[i];j++)scanf("%d",&a),sum[i][j]=sum[i][j-1]+a;
}
for(int i=1;i<=n;i++)for(int j=0;j<=x[i];j++)for(int k=0;k<=j;k++)d[i][j]=max(d[i][j],sum[i][k]+sum[i][x[i]]-sum[i][x[i]-(j-k)]);
for(int i=1;i<=n;i++)for(int j=0;j<=sx[i];j++)for(int k=0;k<=min(j,x[i]);k++)dp[i][j]=max(dp[i-1][j-k]+d[i][k],dp[i][j]);
cout<<dp[n][m]<<endl;
return 0;
}