[HNOI2004] 敲砖块（动态规划）

编程基础 • 2025-10-04 15:46 • 阅读 44

题目来源：洛谷P1437

[HNOI2004] 敲砖块

题目背景

无

题目描述

在一个凹槽中放置了 $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\leq a_{i,j}\leq 100$ 。

对于 $100\%$ 的数据，满足 $1\leq n\leq 50$ ， $1\leq m\leq \frac{n\times(n+1)}{2}$ ；

输出格式

输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。

样例 #1

样例输入 #1

4 5 2 2 3 4 8 2 7 2 3 49

样例输出 #1

这题一眼直接确定是 $d p$ ，关键是如何 $d p$ 。
首先，我们套路的设状态 $f [i] [j] [k]$ 表示最后一个敲的是第 $i$ 行，第 $j$ 列的砖块，一共删了 $k$ 个砖块所能获得的最大价值。然后我们依次枚举 $i, j, k$ ，显然 $i, j$ 可以由 $i - 1, j$ 和 $i - 1, j + 1$ 转移而来，然后。。我们就发现了一个致命问题， $k$ 呢， $k$ 怎么进行状态转移，我们考虑多枚举一维 $l$ 来转移 $k$ ，可是这又出现问题了，在 $f [i - 1] [j] [l]$ 和 $f [i - 1] [j - 1] [k - 1]$ 这两个状态中，两个砖块需要转移的方块是有重复的，也就是说直接相加会寄掉。容斥吗？想想就麻烦。
看来我们套路的转移是有后效性的，需要去转变思路。
重新去分析敲砖块的过程，考虑过程，如果我们要删除 $(i, j)$ 这个方块（ $i$ 不为 $0$ ），那么就需要先删去 $(i - 1, j)$ 和 $(i - 1, j - 1)$ 两个方块，这其实引导我们从后从上的去枚举，这样在删除的时候可以解决前缀问题，其次，我们直接枚举一列删除的终点这样就不会有冲突的情况发生。
具体来说，我们设 $f [i] [j] [k]$ 为从后往前枚举，删除了前 $i$ 列，第 $i$ 列删除了前 $j$ 个，一共删除了 $k$ 个，所能得到的最大价值， $s u m [i] [j]$ 表示第 $i$ 列前 $j$ 行一共的价值。
则有： $f[i][j][k]=\max f[i-1][l][k-j]+sum[i][j]$
注意 $j$ 要从 $0$ 开始枚举，因为本列有可能不选。

#include<bits/stdc++.h> using namespace std; int n,m,a[60][60],f[51][51][2500],sum[100][100],ans; int main() { 
      scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) { 
      for(int j=1;j<=n-i+1;j++) sum[i][j]=sum[i][j-1]+a[j][i]; } memset(f,0xcf,sizeof f); f[n+1][0][0]=0; for(int i=n;i;i--) { 
      for(int j=0;j<=n-i+1;j++) { 
      for(int k=j;k<=m;k++) { 
      for(int l=max(j-1,0);l<=n-i;l++) { 
      f[i][j][k]=max(f[i+1][l][k-j]+sum[i][j],f[i][j][k]); ans=max(ans,f[i][j][k]); } } } } printf("%d",ans); return 0; }

总结，通过转移来判断顺序，消除后效性。

今天的文章 [HNOI2004] 敲砖块（动态规划）分享到此就结束了，感谢您的阅读。