打砖块(brike)

NC210249. 打砖块(brike)

描述

在一个凹槽中放置了 $\ n$ 层砖块，最上面的一层有 $\ n$ 块砖，第二层有 $\ n-1$ 块，……最下面一层仅有一块砖。第 $\ i$ 层的砖块从左至右编号为 $1，2,\dots i$ ，第i层的第j块砖有一个价值 $a[i,j]（a[i,j]\leq 50）$ 。下面是一个有5层砖块的例子：

如果你要敲掉第 $\ i$ 层的第 $\ j$ 块砖的话，若 $\ i=1$ ，你可以直接敲掉它，若 $\ i>1$ ，则你必须先敲掉第 $\ i-1$ 层的第j和第 $\ j+1$ 块砖。
你的任务是从一个有 $n（n\leq 50）$ 层的砖块堆中，敲掉 $(m\leq 500)$ 块砖，使得被敲掉的这些砖块的价值总和最大。

输入描述

数据的第一行为两个正整数，分别表示 ，接下来的第i每行有 个数据，分别表示。

输出描述

第1行：表示被敲掉砖块的最大值总和

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 54ms, 内存消耗: 20320K, 提交时间: 2022-08-12 15:26:03

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[52][52],sum[52][52],f[52][52][6000];
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n-i+1;j++)
	    scanf("%lld",&a[i][j]);
	for(int j=1;j<=n;j++)
	  for(int i=1;i<=n;i++)
	    sum[i][j]=sum[i-1][j]+a[i][j];
	for(int j=1;j<=n;j++)
	  for(int i=0;i<=n;i++)
	    for(int k=i;k<=m;k++)
	      for(int l=0;l<=i+1;l++)
	        f[i][j][k]=max(f[i][j][k],f[l][j-1][k-i]+sum[i][j]);
	cout<<max(f[0][n][m],f[1][n][m]);
	return 0;
}