hdu3016――Man Down - c++编程基础

have carefully selected several similar problems for you: 1542 1828 1540 2871 1698

一开始的写法超时了，然后用线段树优化了下，转移的复杂度降到了O(logn)，总复杂度是O(n * logn)

#include 
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #pragma comment(linker, "/STACK:102400000, 102400000") using namespace std; const int N = 100010; const int inf = 0x3f3f3f3f; int dp[N][2]; int n; struct node { int l, r; int h; int w; }blank[N]; struct node2 { int l, r; int h; int col; }tree[N << 2]; int cmp(node a, node b) { return a.h > b.h; } void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; tree[p].col = -1; if (l == r) { return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); } void update(int p, int l, int r, int val) { if (l <= tree[p].l && tree[p].r <= r) { tree[p].col = val; return; } if (tree[p].col != -1) { tree[p << 1].col = tree[p].col; tree[p << 1 | 1].col = tree[p].col; tree[p].col = -1; } int mid = (tree[p].l + tree[p].r) >> 1; if (r <= mid) { update(p << 1, l, r, val); } else if (l > mid) { update(p << 1 | 1, l, r, val); } else { update(p << 1, l, mid, val); update(p << 1 | 1, mid + 1, r, val); } } int query(int p, int pos) { if (tree[p].l == tree[p].r) { return tree[p].col; } if (tree[p].col != -1) { tree[p << 1].col = tree[p].col; tree[p << 1 | 1].col = tree[p].col; tree[p].col = -1; } int mid = (tree[p].l + tree[p].r) >> 1; if (pos <= mid) { return query(p << 1, pos); } else { return query(p << 1 | 1, pos); } } int main() { while(~scanf("%d", &n)) { memset (dp, -1, sizeof(dp)); int left = inf, right = -inf; for (int i = 0; i < n; ++i) { scanf("%d%d%d%d", &blank[i].h, &blank[i].l, &blank[i].r, &blank[i].w); left = min(left, blank[i].l); right = max(right, blank[i].r); } // printf("%d %d\n", left, right); build(1, left, right); sort (blank, blank + n, cmp); for (int i = n - 1; i >= 0; --i) { int j = query(1, blank[i].l); if (j != -1) { dp[i][0] = max(dp[j][0], dp[j][1]) + blank[j].w; } else { dp[i][0] = 0; } j = query(1, blank[i].r); if (j != -1) { dp[i][1] = max(dp[j][0], dp[j][1]) + blank[j].w; } else { dp[i][1] = 0; } update(1, blank[i].l, blank[i].r, i); } int ans = max(dp[0][0], dp[0][1]) + 100 + blank[0].w; if (ans <= 0) { ans = -1; } printf("%d\n", ans); } return 0; }

hdu3016――Man Down(二)