题目大意:
有n种长宽高为x,y,z的砖头,每种都有无数个。砖头可以用不同方式来盖,砖头a以某种方式可以盖在砖头b上,当且仅当a的底部的长宽都要比b的底部长宽要小。问最高可以建多高?
解题思路:
动态规划中的最长递增(递减)子序列问题,每个砖头可以看成是3个砖头,即A(x,y,z) , B(x,z,y) 和 C(y,z,x),其中前两个为底,大三个元素为高,然后将所有砖头进行排序,长宽小的排前面,即 (x1 < x2 && y1 < y2 ) || ( x1 < y2 && y1 < x2 ) || ( x1*y1 < x2*y2 ), 其中第三个条件为面积小的放前面,当不能满足前两个条件时,若面积大的放前面会出错,具体为什么我没弄清楚,但两者我都试过,必须得把面积小的放前面。
排好序后,接下来就是求最大递增子序列了,只要把原来求子序列长度改为高度即可。状态转移方程为:
dp[i] = max( dp[i], dp[j]+v[i][2] );
其中v[i][2]表示第i个砖头的高度。dp[i]表示第i个砖头能够搭成的最高高度。
代码:
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; bool cmp( vector<int> v1, vector<int> v2 ) { return ( (v1[0]<v2[0] && v1[1]<v2[1]) || ( v1[0]<v2[1] && v1[1]<v2[0] ) || (v1[0]*v1[1] < v2[0]*v2[1]) ); } int dp[30000] = {1}; int main() { freopen( "test.txt", "r", stdin ); int T = 1; int N; int value1, value2, value3; while( cin>>N, N ) { memset(dp,0,sizeof(dp) ); vector<int> temp; vector< vector<int> > v; for( int i = 0; i < N; i++ ) { cin>>value1>>value2>>value3; temp.push_back(value1); temp.push_back(value2); temp.push_back(value3); v.push_back(temp); temp.clear(); temp.push_back(value1); temp.push_back(value3); temp.push_back(value2); v.push_back(temp); temp.clear(); temp.push_back(value2); temp.push_back(value3); temp.push_back(value1); v.push_back(temp); temp.clear(); } sort( v.begin(), v.end(), cmp ); for( int i = 0; i < 3*N; i++ ) { dp[i] = v[i][2]; } for( int i = 3*N-2; i >= 0; i-- ) { for( int j = i+1; j < 3*N; j++ ) { if( ((v[j][0] > v[i][0]) && (v[j][1] > v[i][1])) || ((v[j][0] > v[i][1]) && (v[j][1] > v[i][0])) ) dp[i] = max( dp[i], dp[j]+v[i][2] ); } } sort(dp,dp+(3*N)); cout<<"Case "<<T<<": maximum height = "<<dp[3*N-1]<<endl; T++; } return 0; }
相关推荐
This is the AR sample via BabylonJS
Babylon.JS.Essentials的文档下载,最新Babylon.JS.Essentials.pdf book
blender转babylon插件,Blender2Babylon-2.80x.zip,支持最新的2.9版本
babylon install and key
Babylon6Babylon6Babylon6Babylon6Babylon6Babylon6Babylon6
Blender转Babylon格式插件。 安装步骤见https://doc.babylonjs.com/
maya2019 导出gltf插件 github下载地址 https://github.com/BabylonJS/Exporters/releases 支持max3d、maya导出gltf
Babylon.js源码 Babylon.js源码 Babylon.js源码 Babylon.js源码
Babylon9_setup
babylonjs原生开发包,直接在html中添加便可使用。轻松开发webgl,导入模型文件等等!
Babylon 是一款来自以色列相当优秀的多国语言免费翻译软件,全球顶级的字典及翻译软件Babylon还推出了中文版,并提供免费下载。支持的互译语言有:中文、英文、西班牙文、日文、德文、法文、俄文、意大利文、葡萄牙...
Max2Babylon(3DMax转GFTL)-1.4.2,3Dmax模型转GLTF模型插件
网上流行的许可证文件,可以注册成功,但一不小心你点了升级,或者下载它的字典后,发现许可证不见了,变成... 本人终于找到了能用的keymaker,直接将里面的KEY信息复制到babylon即可。里面包括本人最喜欢的webster词典
方便直接把.glb 丢到官方在线沙盒查看,或者是本地加载配合inspector调试。...https://www.babylonjs-playground.com/#4AJ16M#5 https://www.babylonjs.com/demos/glowingespilit/ https://vernissage.phire.de/
Max2Babylon-0.24.0.zip 3DMax导出.babylon格式文件的插件
来自以色列最强大的英文翻译软件 - Babylon,在全球已有超过 70 个国家 2 千 2 百万人使用。Babylon-Pro 提供最专业英文翻译,有别于一般的翻译软件,Babylon 最迷人的是可外加其它语言字典,提供让您翻译一次可同时...
babylon 8.0 许可证Babylon Pro,一款来自以色列超强大的英文翻译软件,在全球已有超过 72 个国家 2 千 2 百万人使用。Babylon-Pro 提供最专业英文翻译,有别于一般的翻译软件,Babylon 最迷人的是可
Babylon Pro 来自以色列最强大的英文翻译软件 - Babylon Pro,在全球已有超过 70 个国家 2 千 2 百万人使用。Babylon-Pro 提供最专业英文翻译,有别于一般的翻译软件,Babylon 最迷人的是可外加其它语言字典,提供让...
Babylon Pro v9.0.7 r0 Portable 多国语言便携特别版 启动后,直接为已激活状态。 软件大小:10.4M 软件语言:多国语言(含中文) 软件类别:国外软件/词典翻译 运行环境:windows XP/Vista/Win7 Babylon是...
babylon6_duote.rar