洛谷P1437 [HNOI2004]敲砖块(dp)
2018-07-09 13:25:00来源:博客园 阅读 ()
题目背景
无
题目描述
在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖,从上到下每层依次减少一块砖。每块砖
都有一个分值,敲掉这块砖就能得到相应的分值,如下图所示。
14 15 4 3 23
33 33 76 2
2 13 11
22 23
31
如果你想敲掉第 i 层的第j 块砖的话,若i=1,你可以直接敲掉它;若i>1,则你必须先敲掉第
i-1 层的第j 和第j+1 块砖。
你现在可以敲掉最多 m 块砖,求得分最多能有多少。
输入输出格式
输入格式:
输入文件的第一行为两个正整数 n 和m;接下来n 行,描述这n 层砖块上的分值a[i][j],满足
0≤a[i][j]≤100。
对于 100%的数据,满足1≤n≤50,1≤m≤n*(n+1)/2;
输出格式:
输出文件仅一行为一个正整数,表示被敲掉砖块的最大价值总和。
输入输出样例
4 5 2 2 3 4 8 2 7 2 3 49
19
非常妙的一道题目
首先我们最先想到的肯定是$f[i][j][k]$表示第$i$行第$j$列选了$k$个的最大价值
但是这样由于第一行的缘故是有后效性的
转换一下思路,用$f[i][j][k]$表示第$i$列,第$i$个,选了$k$
转移的时候倒着枚举列,这样就不会有后效性了
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> //#define int long long using namespace std; const int MAXN = 1e5 + 10, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, f[51][51][5001], a[5001][5001]; main() { #ifdef WIN32 //freopen("a.in", "r", stdin); #endif N = read(); M = read(); for(int i = 1; i <= N; i++) for(int j = 1; j <= N - i + 1; j++) a[i][j] = read(); memset(f, -0x3f, sizeof(f)); f[N + 1][0][0] = 0; for(int j = N; j >= 1; j--) { int sum = 0; for(int i = 0; i <= N - j + 1; i++, sum += a[i][j]) for(int k = i; k <= M; k++) { for(int l = max(0, i - 1); l <= N - j; l++) f[j][i][k] = max(f[j][i][k], f[j + 1][l][k - i] + sum); } } int ans = 0; for(int i = 1; i <= N; i++) for(int j = 1; j <= N - i + 1; j++) ans = max(ans, f[i][j][M]); printf("%d", ans); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash