本文主要是介绍uva10051（dp 立方体塔， 拆分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个立方体，每一面都有颜色，现在要用他们堆出高度尽量高的塔，条件是，两个接触的块，他们的接触面颜色要一样，同时上面的块重量要严格小于他下面的。
与LIS思想一样，题目给出的数据是按重量递增的
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<cstring>
#include<stack>
#include<string>
#include<set>
#include<fstream>
using namespace std;
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))
#define bug printf("===\n");
#define rep(a,b) for(int i=a;i<b;i++)
#define rep_(a,b) for(int i=a;i<=b;i++)
#define P pair<int,int>
#define X first
#define Y second
#define vi vector<int>
const int maxn=50002;
const int inf=999999999;
typedef long long LL;
void Max(int&a,int b){if(a<b)a=b;}
void Min(int&a,int b){if(a>b)a=b;}int color[6];
char s[6][20]={"front", "back", "left", "right", "top" ,"bottom"};
int dp[maxn];
int f[maxn];
struct node{int top,bom,weight,s;node(){}node(int a,int b,int c,int r):top(a),bom(b),weight(c),s(r){}
}p[maxn];void out(int x){if(x==-1)return ;out(f[x]);printf("%d %s\n",p[x].weight,s[p[x].s]);
}int main(){int n;int cas=0;while(~scanf("%d",&n)&&n){int k=0;for(int i=0;i<n;i++){for(int j=0;j<6;j++){scanf("%d",&color[j]);}for(int j=0;j<6;j++){if(j%2){p[k++]=node(color[j],color[j-1],i+1,j);}else {p[k++]=node(color[j],color[j+1],i+1,j);}}}cl(dp,0);cl(f,-1);int ans=0,index=0;for(int i=0;i<k;i++){for(int j=i+1;j<k;j++)if(dp[j]<dp[i]+1&&p[j].weight>p[i].weight&&p[j].top==p[i].bom){dp[j]=dp[i]+1;f[j]=i;}if(ans<dp[i]){ans=dp[i];index=i;}}if (cas)printf("\n");printf("Case #%d\n%d\n", ++cas, ans + 1);out(index);}return 0;
}/*
3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 1 1 1
10
1 5 10 3 6 5
2 6 7 3 6 9
5 7 3 2 1 9
1 3 3 5 8 10
6 6 2 2 4 4
1 2 3 4 5 6
10 9 8 7 6 5
6 1 2 3 4 7
1 2 3 3 2 1
3 2 1 1 2 3
0
*/这篇关于uva10051（dp 立方体塔， 拆分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
