UVA Live 6122‖UESTC OJ 2326列挙+ソート+LIS

転送ゲート:
UVALive
UESTC OJ
标题:n個の箱があって、長さと幅を知っていて、箱を積み上げて、箱は任意に反転することができて、順序は任意で、上の箱の底面が下の箱の底面を超えてはいけないことを要求して、最大で何個積み上げることができますか.
考え方:まずn<=10で、列挙は容易に考えられますが、ここでは箱ごとにどの面で底面を作るかを列挙します.そうすると、せいぜい3^10種類です.このように列挙した後,各箱の底面の2つの辺長を得た:x 1,y 1;x2,y2;x3,y3;.........,ここではx#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node { int l,w; } p[15],c[15]; int a[15][4]; int n,s[15]; int x[3]= {0,0,1}; int y[3]= {1,2,2}; int ans; bool cmp(node xx,node yy) { if(xx.l==yy.l)return xx.w<yy.w; else return xx.l<yy.l; } void dfs(int u) { if(u==n) { for(int i=0; i<n; i++) { c[i]=p[i]; } sort(c,c+n,cmp); memset(s,0,sizeof(s)); for(int i=0; i<n; i++) { s[i]=1; for(int j=i-1; j>=0; j--) { if(c[i].w>=c[j].w&&s[i]<s[j]+1) { s[i]=s[j]+1; if(ans<s[i])ans=s[i]; } } } return; } for(int i=0; i<3; i++) { p[u].l=a[u][x[i]]; p[u].w=a[u][y[i]]; if(p[u].l>p[u].w)swap(p[u].l,p[u].w); dfs(u+1); } } int main() { int ca=1; while(scanf("%d",&n)&&n) { for(int i=0; i<n; i++) { scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]); } ans=0; dfs(0); cout<<"Case "<<ca++<<": "; cout<<ans<<endl; } return 0; }