题解 P5760 【[NOI1997]积木游戏】
asdfo123
·
·
题解
原题P5760
我们观察题面，思考一下这道题的决策方案
对于当前“状态”，我们有三种“决策”：
这里其实有一个问题，我们如何判断当前块能不能加在之前的块上面？？
我们用a_{i,0},a_{i,1},a_{i,2}分别代表一个块的长，宽，高（相对而言）
那么显然这三条边能构成三个面，为了方便，我们分别定义：
a_{i,4}=a_{i,0}
a_{i,5}=a_{i,1}
那么对于一个长度a_{i,k}:
$a_{i,k+2}$ 为所对应的高
我们定义 $dp_{i,j,l}$ 表示前 $i$ 根柱子，第 $j$ 块积木并且当前正在处理第 $l$ 个平面（我们理解为处理一条边）。
$0 \leq l \leq 2$，分别代表积木不同的三边（面）。
思考完决策，我们开始递推：
**决策1**:新起一堆：
$$dp_{i,j,l}=dp_{i-1,h,k}+a_{j,l+2}$$
这里 $h$ 代表之前的积木，$k$代表之前这个积木的第$k$个面
**决策2**:加在当前堆：
$$dp_{i,j,l}=dp_{i,j,k}+a_{j,l+2}$$
**决策3**:当然是不放
所以我们对前两个决策分别对不放和放取 $max$，开一个 $ans$ 记录最大值就可以了。
还有没太听懂的可以看代码。。。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int a[N][5],ans;
int dp[N][N][5],n,m;
int x1,y1,x2,y2;//用dp[i][j][l]表示第i堆第j块积木第l条边的最大高度
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);//a[i][k+2]是这面所对应的高
a[i][3]=a[i][0];
a[i][4]=a[i][1];
}
for(int i=1;i<=m;i++) //第i根柱子
for(int j=1;j<=n;j++) //第j块积木
for(int h=0;h<j;h++) //在编号小的积木中找第h块积木 (从0开始,否则求不出1的值)
for(int k=0;k<=2;k++) //第h块积木的第k条边
for(int l=0;l<=2;l++) //第j块积木的第l条边
{
x1=max(a[h][k],a[h][k+1]);//下面积木上表面的长边
y1=min(a[h][k],a[h][k+1]);//短边
x2=max(a[j][l],a[j][l+1]);//上面积木下表面的长边
y2=min(a[j][l],a[j][l+1]);//短边
if(x1>=x2&&y1>=y2) //如果下面积木的两条边大于上面积木的两边
dp[i][j][l]=max(dp[i][j][l],dp[i][h][k]+a[j][l+2]); //放或不放，取较大佱
dp[i][j][l]=max(dp[i][j][l],dp[i-1][h][k]+a[j][l+2]); //和前一堆比较
ans=max(ans,dp[i][j][l]);
}
printf("%d",ans);
return 0;
}
```