题解 P1437 【[HNOI2004]敲砖块】

H_D_NULL · 2020-07-20 10:26:15 · 题解

经典DP

思考过程

首先，经过观察，我们发现如果一块砖头被敲，那么其上一层与其相邻的两块砖头也必须被敲，这两块砖头又会影响与它们相邻的上层砖头......就会形成以下一个三角形：

这就相当于DP的一个状态，而且可以预处理，不禁让我们想到了用DP的方法求解。

但是，我们发现敲了多个砖头时，多个三角形可能会产生重叠：

这样就产生了后效性，不符合动态规划的原则。

难道，只有放弃了吗......

振作起来啊！经过观察，我们可以发现即使三角形有重叠，但它们的轮廓线始终保持某种规律，即可看做这几个三角形轮廓线的重叠：

所以我们可以以每个点为状态，最终构造出一条合法的轮廓线，最终达到DP的目的。

对于一个点，它的状态只能从他的左边，左下和左上转移而来，具体的状态转移方程会在代码中呈现。

值得注意的是，这条轮廓线可能不连续，所以要利用状态0来保存之前的合法轮廓线（具体见代码）。

下面上代码：

#include<bits/stdc++.h>
#define re register
using namespace std;

int n,m;
int v[55][55];
int f[55][55][1505];
int ans;

bool vis[55][55][1505];

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=n-i+1;j++){
            cin>>v[i][j];
            v[i][j]+=v[i-1][j];
        }
    }
    for(re int i=1;i<=n;i++){
        vis[i][0][0]=1; //vis数组记录是否合法（也可不用？但用了肯定没错）
        for(re int j=0;j<=n-i+1;j++){ //用0状态来处理不连续的轮廓线
            for(re int p=1;p<=m;p++){
                if(p-j>0){
                    if(vis[i-1][j+1][p-j]){
                        vis[i][j][p]=1;
                        f[i][j][p]=max(f[i][j][p],f[i-1][j+1][p-j]+v[j][i]);
                    }
                    if(vis[i-1][j][p-j]){
                        vis[i][j][p]=1;
                        f[i][j][p]=max(f[i][j][p],f[i-1][j][p-j]+v[j][i]);
                    }
                }
                if(vis[i][j-1][p-1]){
                    vis[i][j][p]=1;
                    f[i][j][p]=max(f[i][j][p],f[i][j-1][p-1]+v[j][i]-v[j-1][i]);
                }
            }
        }
    }
    for(re int i=1;i<=n;i++) ans=max(f[i][1][m],ans); //只有最终到达1层的才是合法的结束状态
    printf("%d",ans);
    return 0;
}