洛谷P1437 [HNOI2004]敲砖块(dp)
洛谷P1437 [HNOI2004]敲砖块(dp)
attack
发布于 2018-07-27 15:12:49
发布于 2018-07-27 15:12:49
题目背景
无
题目描述
在一个凹槽中放置了 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；
输出格式：
输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。
输入输出样例
输入样例#1： 复制
4 5
2 2 3 4
8 2 7
2 3
49输出样例#1： 复制
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;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录