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≤a[i][j]≤100。

对于 100%的数据，满足1≤n≤50，1≤m≤n*(n+1)/2；

输出格式：

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

输入输出样例

输入样例#1： 复制

输出样例#1： 复制


看这位大佬的题解写的  https://www.cnblogs.com/Mrsrz/p/7257290.html

我们先把砖块“左对齐”，然后敲掉砖块（i，j）（i>1）时，就必须先敲掉（i-1，j）和（i-1，j+1）。

设 $f [i] [j] [k]$ 表示打到第i列第j块砖（且这块砖必须选），一共打了k块砖时所得的分数，则有

$f [i] [j] [k] = m a x (f [i] [j] [k], f [i + 1] [p] [k - j] (j - 1 \leq p < n - i + 1) + \sum_{v = 1}^{j} a [v] [i])$

其中求第i列前v块砖之和可以直接预处理出来。因为求第i列时要用到第i+1列的东西，所以枚举i时应该从大到小。

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000
typedef long long ll;
#define inf 2147483647
#define ri register int

int n, m;
int a[55][55];
int sum[55][55];
int dp[55][55][2000];
int ans = 0;
int x;

int main() {
  ios::sync_with_stdio(false);
  // freopen("test.txt", "r", stdin);
  //  freopen("outout.txt","w",stdout);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n - i + 1; j++){
      cin>>x;
      sum[j][i]=sum[j][i-1]+x;
    }
  memset(dp, -1, sizeof(dp));
  dp[n + 1][0][0] = 0;
  for (int i = n; i >= 1; i--)
    for (int j = 0; j <= n-i+1; j++) //这里因为可以不选所以从0开始
      for (int k = j * (j + 1) / 2; k <= m; k++) //k最小就是这个位置向上形成的三角形
        for (int p = (j) ? j - 1 : 0; p <= n - i; p++) //p为0特殊处理
          if (dp[i + 1][p][k - j] != -1) {
            dp[i][j][k] = max(dp[i][j][k], dp[i + 1][p][k - j] + sum[i][j]);
            ans = max(ans, dp[i][j][k]);
          }
  cout << ans;

  return 0;
}

我们先把砖块“左对齐”，然后敲掉砖块（i，j）（i>1）时，就必须先敲掉（i-1，j）和（i-1，j+1）。

设 $f [i] [j] [k]$ 表示打到第i列第j块砖，一共打了k块砖时所得的分数，则有 $f [i] [j] [k] = m a x (f [i] [j] [k], f [i + 1] [p] [k - j] (j - 1 \leq p < n - i + 1) + \sum_{v = 1}^{j} a [v] [i])$ 。其中求第i列前v块砖之和可以直接预处理出来。因为求第i列时要用到第i+1列的东西，所以枚举i时应该从大到小。