自动搬运

查看原文

来自洛谷，原作者为

	asdfo123 An unexperienced Acmer

搬运于2025-08-24 22:14:07，当前版本为作者最后更新于2020-10-13 11:10:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题P5760

我们观察题面，思考一下这道题的决策方案

对于当前“状态”，我们有三种“决策”：

• 从当前块另起一堆
• 当前块加在前一堆上
• 不选当前块

这里其实有一个问题，我们如何判断当前块能不能加在之前的块上面？？

我们用$a_{i,0},a_{i,1},a_{i,2}$分别代表一个块的长，宽，高（相对而言）

那么显然这三条边能构成三个面，为了方便，我们分别定义：

那么对于一个长度$a_{i,k}$:

$a_{i,k+1}$ 为所对应的宽

$a_{i,k+2}$ 为所对应的高

我们定义 $dp_{i,j,l}$ 表示前 $i$ 根柱子，第 $j$ 块积木并且当前正在处理第 $l$ 个平面（我们理解为处理一条边）。 $0 \leq l \leq 2$，分别代表积木不同的三边（面）。

思考完决策，我们开始递推：

决策1:新起一堆：

这里 $h$ 代表之前的积木，$k$代表之前这个积木的第$k$个面

决策2:加在当前堆：

决策3:当然是不放

所以我们对前两个决策分别对不放和放取 $max$，开一个 $ans$ 记录最大值就可以了。

还有没太听懂的可以看代码。。。

#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;
}