Tower of Cubes UVA - 10051
类似于最长上升子序列
题目描述：要求把给出的小正方体尽量排得更高，要求是：下面的小正方体的重量要大于上面小正方体的重量，且相邻的正方体上面的地面要和下面的顶面颜色相同，求最大高度，并打印小正方体的排放，依次从上到下打印小正方体的序号和那个面朝上。
解题分析：刚学了最长上升子序列，听说这个题是，才开始做的。读完题蒙蔽了，后来一想，是我被裸地最长上升子序列给固化了。大家可以这样想，最长上升子序列不只是自然数字的序列啊，它同样可以是人为定义的某种条件和要求，只要定义的这个要求满足最长上升子序列的性质，就都可以用这个解法。在这个题中，”上升子序列“就是指相同颜色的上下面的个数。因为只考虑上下面，所以可以把一个正方形拆成6个，每个拆出来的正方体只有上面和下面，它的重量，和它在原正方形中的面。用一个path数组记录的是“类上升子序列”的前一个节点。最后递归打印即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 5000 + 10;
struct Cube
{
int bot,top,w,face;
Cube(int a,int b,int c,int d):bot(a),top(b),w(c),face(d){}
};
const char str[10][100] = {"<-_->","front","back","left","right","top","bottom"};
int dp[maxn];
int color[maxn];
vector<Cube> C;
int path[maxn];//记录的是“类上升子序列”的前一个节点
void init()
{
C.clear();
memset(dp,0,sizeof(dp));
memset(path,-1,sizeof(path));
}
void print(int i)
{
if(path[i] == -1)
{
printf("%d %s\n",C[i].w,str[C[i].face]);
return;
}
else
{
print(path[i]);
printf("%d %s\n",C[i].w,str[C[i].face]);
}
}
int main()
{
int N;
int kase = 0;
while(scanf("%d",&N)==1&&N)
{
if(kase) puts("");
init();
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= 6; j++)
{
scanf("%d",&color[j]);
if(!(j&1))//将一个正方体拆成6个正方体
{
C.push_back((Cube){color[j-1],color[j],i,j-1});
C.push_back((Cube){color[j],color[j-1],i,j});
}
}
}
for(int i = 0; i < C.size();i++)//在上面的方块
{
dp[i] = 1;
for(int j = 0; j < i; j++)//在下面的方块
{
if(C[i].w > C[j].w && C[i].bot == C[j].top)
{
if(dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
path[i] = j;
}
}
}
}
int index;
int ans = -1;
for(int i = 0;i < C.size();i++)
{
if(dp[i] > ans)
{
ans = dp[i],index = i;
}
}
printf("Case #%d\n%d\n",++kase,ans);
print(index);
}
return 0;
}
