HDU 4001 DP LIS-白红宇

HDU 4001 DP LIS

阅读量：2442 次

发布时间：2019-05-10

本文共 3086 字，大约阅读时间需要 10 分钟。

/*******************************************************************************   大连网络赛的DP水题，但是当时我们队没过，其实本质跟HDU第一页的那个Monkey and Banana没啥区别。。。一开始用栈存储，YY是普通的LIS，结果无限WA，现在想来，这题的block排完序后，也谈不上什么单不单调的，用栈是不靠谱。。。具体解法就是先把block排下序，width从小到大，length从小到大，kind从大到小，这样是为了保证DP时不出现无法构造Skyscraper，这个可以体会一下，然后这里可以设个哨兵，方便后面的比较，接着就是DP了，DP数组记录的是第i个block能得到的最高的高度，然后通过比较i之前的block就能得到最后的结果了～*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 1004;int n;LL dp[MAXN];struct Node{ int width; int length; int thickness; int kind; Node() { CLR(this, 0); } LL area() { return SC(LL, width) * SC(LL, length); }}blocks[MAXN];bool cmp(const Node & na, const Node & nb){ if (na.width != nb.width) { return na.width < nb.width; } if (na.length != nb.length) { return na.length < nb.length; } return na.kind > nb.kind;}bool judge(Node & pre, Node & crt){ switch (crt.kind) { case 0: return crt.width >= pre.width && crt.length >= pre.length; break; case 1: return crt.width >= pre.width && crt.length >= pre.length && crt.area() > pre.area(); break; case 2: return crt.width > pre.width && crt.length > pre.length; break; default: break; } return false;}void ace(){ const Node unit = Node(); while (cin >> n, n) { for (int i = 0; i < n; ++i) { cin >> blocks[i].width >> blocks[i].length >> blocks[i].thickness >> blocks[i].kind; } for (int i = 0; i < n; ++i) { if (blocks[i].width > blocks[i].length) { swap(blocks[i].width, blocks[i].length); } } blocks[n++] = unit; //哨兵～～～ sort(blocks, blocks + n, cmp); CLR(dp, 0); for (int i = 1; i < n; ++i) { dp[i] = blocks[i].thickness; //细节 for (int j = i - 1; j >= 0; --j) { if (!judge(blocks[j], blocks[i])) { continue ; } dp[i] = max(dp[i], dp[j] + blocks[i].thickness); } } LL res = 0; for (int i = 0; i < n; ++i) { res = max(res, dp[i]); } cout << res << endl; } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif ace(); return 0;}/*310 10 12 010 10 12 110 10 11 2210 10 11 110 10 11 134 8 1 04 9 2 15 6 4 124 8 1 05 7 2 0*/