iis7网站绑定域名,手机制作ppt用什么软件,王烨飞微博,天津建设网工程信息网题目:堆盒子
礼盒大小不同#xff0c;我们玩堆盒子的游戏#xff0c;怎么堆盒子使得堆出的高度最高#xff0c;每个礼盒的大小由长、宽、高表示#xff0c;堆盒子的时候要求下面的盒子长、宽、高都必须大于上面的盒子#xff0c;不包含等于。高度为堆出的礼盒的所有高度的…题目:堆盒子
礼盒大小不同我们玩堆盒子的游戏怎么堆盒子使得堆出的高度最高每个礼盒的大小由长、宽、高表示堆盒子的时候要求下面的盒子长、宽、高都必须大于上面的盒子不包含等于。高度为堆出的礼盒的所有高度的总和。
输入描述
输入的第一行是礼盒的个数N
接下来输入N行每行表示每个礼盒的长、宽、高。
礼盒的数量不超过1000个每个盒子的长、宽、高取值范围为1~10。
输出描述
输出一行输出能堆出盒子的最高高度
样例
输入
4
1 1 1
2 3 4
3 6 7
4 5 6输出
12说明
选择1、2、33个盒子堆出的高度最高14712
题目分析
【题目类型动态规划多维动规】
我们按照盒子从小到大的顺序计算动态规划维护一个DP[l][w][h]的三维数组用来描述最大的盒子的尺寸为l、w、h时的最大总高度。
状态转移方程为如果存在高度为h的盒子那么DP[l][w][h] max(DP[l-1][w][h], DP[l][w-1][h],DP[l][w][h-1], DP[l-1][w-1][h-1]h )若不存在则去掉最后一种情况DP[l][w][h] max(DP[l-1][w][h], DP[l][w-1][h],DP[l][w][h-1])
代码
n int(input())
grid [[[] for _ in range(11)] for __ in range(11)]
DP [[[0 for _ in range(11)] for __ in range(11)] for ___ in range(11)]
for _ in range(n):l, w, h map(int,input().split())grid[l][w].append(h) # for g in grid:
# print(g)for l in range(1, 11):for w in range(1, 11):for h in range(1, 11):if h in grid[l][w]:DP[l][w][h] max(DP[l-1][w][h], DP[l][w-1][h], DP[l][w][h-1], DP[l-1][w-1][h-1]h)else:DP[l][w][h] max(DP[l-1][w][h], DP[l][w-1][h], DP[l][w][h-1])print(max(DP[10][10]))
