打砖块(codevs 1257)
2024-09-01 11:23:18
题目描述 Description
在一个凹槽中放置了n层砖块,最上面的一层有n块砖,第二层有n-1块,……最下面一层仅有一块砖。第i层的砖块从左至右编号为1,2,……i,第i层的第j块砖有一个价值a[i,j](a[i,j]<=50)。下面是一个有5层砖块的例子。如果你要敲掉第i层的第j块砖的话,若i=1,你可以直接敲掉它,若i>1,则你必须先敲掉第i-1层的第j和第j+1块砖。
你的任务是从一个有n(n<=50)层的砖块堆中,敲掉(m<=500)块砖,使得被敲掉的这些砖块的价值总和最大。
输入描述 Input Description
你将从文件中读入数据,数据的第一行为两个正整数,分别表示n,m,接下来的第i每行有n-i+1个数据,分别表示a[i,1],a[i,2]……a[i,n – i + 1]。
输出描述 Output Description
输出文件中仅有一个正整数,表示被敲掉砖块的最大价值总和。
样例输入 Sample Input
4 5
2 2 3 4
8 2 7
2 3
49
样例输出 Sample Output
19
数据范围及提示 Data Size & Hint
敲掉第一层的四块砖,再敲掉第二层的第一块砖,2+2+3+4+8=19
/*
直接做DP可能是不好做的,因为一个块是否能被打,还取决于别的块,也就是说,有后效性,那怎么办呢?
我们发现如果某个块被打下来的话,它上面的所有的块一定都被打下来了,所以我们可以将图旋转90°。
设f[i][j][k]表示前i行(旋转之后的行),选了j个,第i行选前k个的最大值。
转移方程:f[i][j][k]=max(f[i-1][j-p][p]+sum[i][k])(sum[i][k]是第i行选前k个的价值)。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 60
using namespace std;
int a[N][N],sum[N][N],f[N][N*][N],n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=n-i+;j++)
scanf("%d",&a[i+j-][i]);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
sum[i][j]=sum[i][j-]+a[i][j];
memset(f,-/,sizeof(f));
f[][][]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=j;k++){
for(int p=max(,k-);p<=i-;p++)
f[i][j][k]=max(f[i-][j-k][p]+sum[i][k],f[i][j][k]);
}
int ans=;
for(int i=;i<=n;i++)
for(int k=;k<=m;k++)
ans=max(ans,f[i][m][k]);
printf("%d",ans);
return ;
}
最新文章
- 无法对 索引 &#39;IndexName&#39; 执行 删除,因为它不存在,或者您没有所需的权限。
- jsp页面添加一个集合数组到action(用序列化提交)
- linux命令(10)使用kill杀死含有指定关键字的进程
- iOS-CoreImage简单使用
- Android虚拟环境的工具集Genymotion完整安装教程
- 水题~~~~HDU 4788
- HDU 1039 -Easier Done Than Said?
- 大并发连接的oracle在Linux下内存不足的问题的分析(转)
- Android中利用Handler实现消息的分发机制(三)
- Linux下mysql远程连接问题
- 我的Python学习笔记(一):==和is
- Graph(Floyd)
- ResNet
- 尝鲜svnup
- Python—re模块
- Hibernate的学习(二)
- python zip压缩文件 并移动到指定目录
- 阿里云slb+https 实践操作练习
- HDUOJ--2079选课时间(题目已修改,注意读题)
- JSP,PHP,Python,Ruby,Perl概要及各自特点