2013年10月10日 星期四

UVA 103 Stacking Boxes

[LIS+DFS]
用TOP_DOWN的方式就OK了
不過用拓樸排序壓扁應該也可以。
要找一個線性的檢查方式去確認BOX_A是否可放入BOX_B
若BOX_B內可置入一個BOX_A，則 BOX_B的vec最小值必然大於BOX_A的vec最小值(要不然矛盾)，因此，只需要把vec排序後再做比較即可。



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
class box
{
public:
 int vec[10];
 int d;
 box()
 {
  memset(vec,0,sizeof(vec));
  d=0;
 }
 void setup(int _d,int _v[10])
 {
  d=_d;
  for(int lx=0;lx<d;lx++)
   vec[lx]=_v[lx];
  sort(vec,vec+d);
 }
 bool operator>(box _a)
 {
  bool ok=true;
  for(int lx=0;lx<d;lx++)
   if(_a.vec[lx]>=vec[lx])
    ok=false;
  return ok;
 }
};
box bs[30];
bool to[30][30];
int n,d;
void GetLIS(int index,vector<int>& re)
{
 bool sum=false;
 re.clear();
 re.push_back(index+1);
 for(int lx=0;lx<n;lx++)
  sum=(sum||to[index][lx]);
 if(sum==false)
  return;
 vector<int> prc(re);
 for(int lx=0;lx<n;lx++)
 {
  if((to[index][lx]))
  {
   GetLIS(lx,prc);
   if(prc.size()>=re.size())
   {
    re=prc;
    re.push_back(index+1);
   }
  }
 }
 return;
}
int main()
{

 while(scanf("%d %d",&n,&d)!=EOF)
 {
  for(int lx=0;lx<n;lx++)
  {
   int vec[10];
   for(int ly=0;ly<d;ly++)
    scanf("%d",&vec[ly]);
   bs[lx].setup(d,vec);
  }
  memset(to,false,sizeof(to));
  for(int lx=1;lx<n;lx++)   //建表
  {
   for(int ly=0;ly<lx;ly++)
   {
    if(bs[lx]>bs[ly])
    {
     to[lx][ly]=true;
     to[ly][lx]=false;
    }
    else if(bs[ly]>bs[lx])
    {
     to[ly][lx]=true;
     to[lx][ly]=false;
    }
   }
  }
  vector<int>mm,prc;
  mm.push_back(1);
  for(int lx=0;lx<n;lx++)
  {
   GetLIS(lx,prc);
   if(mm.size()<prc.size())
    mm=prc;
  }
  printf("%d\n",mm.size());
  for(int lx=0;lx<mm.size();lx++)
   printf("%d%c",mm[lx],((lx==(mm.size()-1)) ? '\n':' '));
 }
 return 0;
}
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)