uva 437 动态规划 lrj - P269

el/2024/2/25 22:25:12

题意:

给出不超过30个立方体,每一种有无穷多个。

要求这些立方体堆成一个尽量搞的柱子,使得每一个立方体下面的立方体的底面长宽都大于上面的底面长宽

题解:

很明显我们可以将每个立方体当做3个或者6个不一样的不可以旋转的长方体

下面代码当做6个,是为了方便计算,这样在判断的过程中不需要加太多条件

而且数据量不大,可以这样做


dp思想:

01背包的思想,放与不放,最后求一个最大值就行了

不能直接取dp【m-1】,因为我们不知道最后一个立方体用了还是没有用


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;struct node
{int x,y,z;node(){}node(int x_,int y_,int z_){x=x_,y=y_,z=z_;}
}blocks[200];
int dp[200];bool cmp(node x1,node x2){return x1.x*x1.y<x2.x*x2.y;
}int main()
{int cases=1,n,a,b,c;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n){int m=0;for(int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);blocks[m++]=node(a,b,c);blocks[m++]=node(b,a,c);blocks[m++]=node(c,b,a);blocks[m++]=node(b,c,a);blocks[m++]=node(a,c,b);blocks[m++]=node(c,a,b);}sort(blocks,blocks+m,cmp);int ans=0;for(int i=0;i<m;i++){dp[i]=blocks[i].z;for(int j=0;j<i;j++){if(blocks[i].x>blocks[j].x&&blocks[i].y>blocks[j].y)dp[i]=max(dp[i],dp[j]+blocks[i].z);}ans=max(ans,dp[i]);}printf("Case %d: maximum height = %d\n",cases++,ans);}return 0;
}



http://www.ngui.cc/el/4895179.html

相关文章

uva 1347 动态规划DAG lrj-P269

题意&#xff1a; 给出按照 x 坐标排序的一系列二维坐标上的点&#xff0c;让你通过来回走一圈&#xff0c;把所有点都恰好走一遍&#xff0c;除了最左端和最右端的点 使得总路程最短 题解&#xff1a; 让两个人同时走&#xff0c;并且不重合&#xff0c;从左边开始走道…

uva 116 动态规划 多阶段决策问题 路径记录 lrj-P270

题意&#xff1a; 给定一个n*m的矩阵&#xff0c;要求从第一列的任何一行出发&#xff0c;每次沿右或右下或右上到达后面一列&#xff0c;最后到第m列任何一行整个路程的最小值&#xff0c;并且要求是字典序最小的 题解&#xff1a; 动态规划 每一列是一个阶段&#xff…

uva 12563 01背包 两个最优条件 lrj-P274

题意&#xff1a; 给你 t 秒时间&#xff0c;有n首歌&#xff0c;每一首歌的时间不超过三分钟&#xff0c;在结束之前唱一首678秒的劲歌金曲 选了一首歌就一定要唱完 并且在保持唱的歌曲数量最多的情况下&#xff0c;时间最长 题解&#xff1a; 虽然 t 的范围很大&…

uva 11400 lrj-P275 动态规划

题意&#xff1a; 见刘汝佳入门书籍 P275 dp[i]min(dp[i],dp[j-1](sum[i]-sum[j-1])*a[i].ca[i].k);题解&#xff1a; 见刘汝佳入门书籍 P275 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std;int dp[1010],sum[1010]; s…

密码生成器+随机数生成器

随机数生成器 0~RAND_MAX之间的随机数程序 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() {srand((unsigned)time(NULL));for(int i = 0; i < 10; i++ )cout << rand() << \t;cout << …

uva 10003 lrj-P278 区间dp入门

题意&#xff1a; 给出一根棍子的长度&#xff0c;以及n个需要切割的点&#xff0c;每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解&#xff1a; 区间dp dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[j]-a[i]); i 为区间左端点&#xff0c;j 为右端点…

Uva-1626 lrj-P278 区间dp

题意&#xff1a; 给定一个由[,],(,)&#xff0c;构成的字符串&#xff0c;给其添加这些括号使得其成为一个正规括号序列 1 空序列是正规括号序列 2 如果S是正规括号序列&#xff0c;那么[S]和(S)也是正规括号序列 3 如果A和B都是正规括号序列&#xff0c;则AB也是正规…

uva 1331 lrj-P279 三角剖分+区间dp

题意&#xff1a; 给出多边形&#xff0c;找出最大三角形面积最小的三角剖分 输出最大的三角形面积 题解&#xff1a; 仔细研究可以知道&#xff0c;第一个点和最后一个点组成的边&#xff0c;一定是在某一个三角形中 那么我们就通过这个边作为基准&#xff0c;任选一个…

uva 12186 lrj-P282 简单树形dp

题意&#xff1a; 某个人签字的话,他的直属下属里必须有至少T%的人签字,问让老板签字最少需要多少工人签字 题解&#xff1a; 树形dp 以老板为根节点&#xff0c;从小往上&#xff0c;递归计算答案即可 #include<vector> #include<stdio.h> #include<st…

uva 1220 lrj-P282 最大独立集(树形dp)

题意&#xff1a; 给出一个树形结构&#xff0c;除了老板外&#xff0c;每一个员工都有直属上司&#xff0c;在其中挑选了员工&#xff0c;就不能挑选他的上司 问这样的挑选方法最多可以挑选多少人&#xff0c;方案是否唯一 题解&#xff1a; 仔细划分即可 当前节点若选…