跳到主要內容

Stacking Boxes

#include
#include
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
#define BOX_SWAP(x,y) {box_t t; t = x; x = y; y = t;}
typedef struct{
int no;
int edge[12];
}box_t;
using namespace std;
int Greater(box_t b1,box_t b2,int dim){
int i;

for(i=0;i<dim;i++){
/*cout<<b1.edge[i]<<" and "<<b2.edge[i]<<endl;*/
if(b1.edge[i]<=b2.edge[i])return 0;
}
return 1;
}
void sort_box(box_t box[],int box_num,int dim){
int i,j;
for(i=0;i<box_num;i++){
for(j=i+1;j<box_num;j++){
if(Greater(box[i],box[j],dim))BOX_SWAP(box[i],box[j]);
}
}
}
void sort_edge(box_t box[],int box_num,int dim){
int i,j,k;
for(i=0;i<box_num;i++){
for(j=0;j<dim-1;j++){
for(k=j+1;kbox[i].edge[k])SWAP(box[i].edge[j],box[i].edge[k]);
}
}
}
}
void print_LIS(int x,int prev[],box_t box[],int choose){
if(prev[x]!=-1)print_LIS(prev[x],prev,box,1);
if(choose==0){
cout<<box[x].no<<endl;
}
else{
cout<<box[x].no<<" ";
}

}
int LIS(box_t box[],int prev[],int box_num,int dim){
int array[32];
for(int i=0;i<box_num;i++){prev[i]=-1;array[i]=1;}
for(int i=0;i<box_num;i++){
for(int j=i+1;jarray[j]){
/*puts("have2");*/
array[j]=array[i]+1;
prev[j]=i;
}
}
}
}
int ans=0,pos=0;
for(int i=0;i<box_num;i++){
/*cout<<prev[i]<<"array"<<array[i]<<endl;*/
if(ans<array[i]){ans=array[i];pos=i;}
}
cout<<ans<>box_num){
cin>>dim;
for(i=0;i<box_num;i++){
box[i].no=i+1;
for(j=0;j>box[i].edge[j];
}
}
sort_edge(box,box_num,dim);
sort_box(box,box_num,dim);
LIS(box,prev,box_num,dim);
}

/*system("PAUSE");*/
return EXIT_SUCCESS;
}

留言