题目大意:
有N个立方体,立方体的6个面颜色不一,现在要求立方体按照体重从小到大叠起来,并且两个立方体接触面的颜色必须相同,求最高能叠多高?
解题思路:
动态规划,本质上就是求最长递增子序列,同时加上了限制条件,就是两个立方体之间颜色要一样,所以我就先用动态规划求出最长符合要求的子序列的长度,同时记录序列最后一个元素的位置,然后再用递归输出子序列。求最长递增子序列的状态转移方程就不写了,直接看代码里面就有,就那么一行,主要就是在状态转移的时候加上判断条件,判断颜色是否一样,然后记录子序列最后一个元素用来递归用。递归的时候也一样,先要判断颜色。
代码:
#include <iostream> #include <vector> #include <cstring> #include <string> #include <algorithm> using namespace std; vector<int> temp; vector< vector<int> > v; int dp[510][6]; char director[6][7]={"front", "back", "left", "right", "top", "bottom"}; void printPath(int ans, int pos, int posK) { if( ans <= 0 ) { cout<<pos+1<<" "<<director[posK]<<endl; return ; } for( int j = pos-1; j >= 0; j-- ) { for( int k = 0; k < 6; k++ ) { if( v[pos][posK] == v[j][k] && dp[j][k%2?k-1:k+1]+1 == ans && ans >= 0 ) { ans--; printPath( ans, j, k%2?k-1:k+1 ); cout<<pos+1<<" "<<director[posK]<<endl; return; } } } return; } int main() { freopen("test.txt", "r", stdin ); int N, color; int T = 1; while( cin>>N, N ) { memset( dp, 0, sizeof( dp ) ); memset( path, -1, sizeof( path ) ); for( int i = 0; i < N; i++ ) { for( int j = 0; j < 6; j++ ) { cin>>color; temp.push_back(color); } v.push_back(temp); temp.clear(); } int ans = 0, pos, posK, tempH = 0; for( int i = 1; i < N; i++ ) { for( int j = 0; j < i; j++ ) { for( int k = 0; k < 6; k++ ) { for( int h = 0; h < 6; h++ ) { tempH = h%2?h-1:h+1; //求出h面的另一面 if( v[i][k] == v[j][h] ) { dp[i][k] = max(dp[j][tempH]+1,dp[i][k]); if( dp[i][k] > ans ) { ans = dp[i][k]; pos = i; //记录最后一个立方体的位置 posK = k;//记录最后一个立方体朝上的那个面 } } } } } } int test = 1; cout<<"Case #"<<T<<endl<<ans+1<<endl; printPath(ans, pos, posK); cout<<endl; v.clear(); T++; } return 0; }
相关推荐
marching_cubes_jgt
MarchingCubes-main算法的C++实现
united_cubes_of_america
Marching Cubes: A High Resolution 3D Surface Construction Algorithm
Marching Cubes Module Marching Cubes Module Marching Cubes Module
1.在MATLAB中直接实现Marching Cubes; 2.使用了向量化和预分配的概念在MATLAB中优化; 3.用c-mex函数和GPU实现.
三维重建算法marching cubes,简称MC算法 的详细解释,比较易懂
关于Marching Cubes的众多教程 基于OpenGL
如何使用matlab调用marchingcubes,某校的某课的课程设计可能会用得到哦
运输行业PPT模板united_cubes_of_america004
球体的Marching Cubes实现
介绍了marching cubes算法
简单易懂讲解Marching Cubes算法,基于OpenGL,可以显示三维的标量场,动画讲解,可以直接复制到VS直接运行。
基于marching cubes的三维重建方法,效果很不错,当然还有很多需要改进的地方
Algorithms for Solving Rubik's Cubes
We present a new algorithm, called marching cubes, that creates triangle models of constant density surfaces from 3D medical data. Using a divide-and-conquer approach to generate inter-slice ...
Möbius cubes的交叉数,闫晓霞,杨元生,直连网络在多处理机、并行计算机系统、大规模集成电路等领域应用广泛。Mobius cubes(MQn)是一类重要的直连网络。本论文使用算法找到MQn�
matlab开发-MarchingCubes。用矢量化行进立方体算法从三维矩阵中计算等距面三角网格
Marching_Cubes算法原理。根据体数据提取等值面~