[HNOI2004]敲砖块 解题报告

[HNOI2004]敲砖块

题目链接

P1437 敲砖块

解题报告

很自然地，看到这道题我们会想到数字三角形。可惜的是，我们发现：不能简单地将一个点的左上角与右上角的值进行比较，因为选择数可能会有重叠。

不妨画画图，看看我们选择的是怎样一个图形把。

*****
****
***
**
*

比如上面这个东西。

#####
####
#*#
**
*

我们发现，选择的数永远是若干个三角的重叠。我们考虑按照这个轮廓进行转移。令 $sum(i,j)$ 表示以 $(i,j)$ 为左下角的一条斜线的值的和，而 $cnt(i,j)$ 则表示个数。 $f(i,j,k)$ 表示选择到 $(i,j)$ ，选择了 $k$ 个的最大和。

则有

$$f(i,j,k)\leftarrow f(i+1,j-1,k)$$

$$f(i,j,k)\leftarrow f(i-1,j,k-cnt(i,j))+sum(i,j)$$

注意边界，注意初值。

#include
#include
#include
using namespace std;
typedef long long ll;
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
ll read() {ll x = 0, f = 1; char ch = getchar();for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');return x * f;
}
const int MAXN = 55;
const int MAXM = 2505;
const int pINF = 0xc1c1c1c1;
int n, m, a[MAXN][MAXN];
int sum[MAXN][MAXN], cnt[MAXN][MAXN];
int f[MAXN][MAXN][MAXM];
int main() {n = read(); m = read();for(int i = 1; i <= n; i++)for(int j = 1; j <= n-i+1; j++)a[i][j] = read();for(int j = n; j >= 1; j--)for(int i = 1; i <= n-j+1; i++)sum[i][j] = sum[i-1][j+1] + a[i][j], cnt[i][j] = cnt[i-1][j+1] + 1;memset(f, 0xc1, sizeof f);f[0][0][0] = 0;for(int j = 1; j <= n+1; j++) {for(int k = 0; k <= m; k++) f[0][j][k] = max(f[0][j-1][k], f[1][j-1][k]);for(int i = 1; i <= n-j+1; i++)for(int k = 0; k <= m; k++) {f[i][j][k] = max(f[i][j][k], f[i+1][j-1][k]);if(k >= cnt[i][j]) f[i][j][k] = max(f[i][j][k], f[i-1][j][k-cnt[i][j]] + sum[i][j]);}}int ans = 0;for(int k = 0; k <= m; k++) ans = max(ans, f[0][n+1][k]);printf("%d\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！