题解 P1437 【[HNOI2004]敲砖块】
H_D_NULL
2020-07-20 10:26:15
## 经典DP
------------
### 思考过程
首先，经过观察，我们发现如果一块砖头被敲，那么其上一层与其相邻的两块砖头也必须被敲，这两块砖头又会影响与它们相邻的上层砖头......就会形成以下一个三角形：
这就相当于DP的一个状态，而且可以预处理，不禁让我们想到了用DP的方法求解。
但是，我们发现敲了多个砖头时，多个三角形可能会产生重叠：
这样就产生了后效性，不符合动态规划的原则。
难道，只有放弃了吗......
振作起来啊！经过观察，我们可以发现即使三角形有重叠，但它们的轮廓线始终保持某种规律，即可看做这几个三角形轮廓线的重叠：
所以我们可以以每个点为状态，最终构造出一条合法的轮廓线，最终达到DP的目的。
对于一个点，它的状态只能从他的左边，左下和左上转移而来，具体的状态转移方程会在代码中呈现。
值得注意的是，这条轮廓线可能不连续，所以要利用状态0来保存之前的合法轮廓线（具体见代码）。
下面上代码：
```cpp
#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;
}
```