HDU5406---CRB and Apple（ DP） 2015 Multi-University Training Contest 10

题意比较简单，

dp[i][j] 表示上一次男女吃的deliciousness分别为i, j的时候的吃的最多的苹果。

那么dp[i][j] = max(dp[i][k] + 1), 0 < k <= j

dp[i][j] = max( max(dp[k][j]) + 1 ) ， 0 < k <= i

对于第一个式子最大值用树状数组线段树都可以解决，第二个式子如果每次从0遍历到i再找最值的话，显然会超时。

仔细想想便可以发现第二个最值和第一个是一样的。这个不好解释。像是对称性那种一样。

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXN = ;

 struct Node{

     int h, d;

     bool operator < (const Node &rhs)const{

         return h != rhs.h ? h > rhs.h : d < rhs.d;

     }

 }apple[MAXN];

 int arr[MAXN<<][MAXN<<];

 int MAX;

 inline int lowbit (int x){

     return x & -x;

 }

 void Modify (int x, int y, int d){

     while (y < MAX){

         arr[x][y] = max(arr[x][y], d);

         y += lowbit(y);

     }

 }

 int query (int x, int y){

     int res = ;

     while (y){

         res = max(arr[x][y], res);

         y -= lowbit(y);

     }

     return res;

 }

 int lsh[MAXN << ], lshtot, tmp[MAXN << ];

 int main()

 {

     int T, n;

     scanf ("%d", &T);

     while (T--){

         scanf ("%d", &n);

         lshtot = ;

         for (int i = ; i < n; i++){

             scanf ("%d%d", &apple[i].h, &apple[i].d);

             lsh[lshtot++] = apple[i].d;

         }

         sort (apple, apple+n);

         sort (lsh, lsh+lshtot);

         lshtot = unique(lsh, lsh+lshtot) - lsh;

         for (int i = ; i < n; i++){

             apple[i].d = lower_bound(lsh, lsh+lshtot, apple[i].d) - lsh + ;

         }

         MAX = lshtot + ;

         memset(arr, , sizeof (arr));

         for (int i = ; i < n; i++){

             for (int j = ; j <= lshtot+; j++){

                 tmp[j] = query(j, apple[i].d);

             }

             for (int j = ; j <= lshtot+; j++){

                 Modify(apple[i].d, j, tmp[j]+);

                 Modify(j, apple[i].d, tmp[j]+);

             }

         }

         int ans = ;

         for (int i = ; i <= lshtot+; i++){

             ans = max(ans, query(i, lshtot+));

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

HDU5406---CRB and Apple（ DP） 2015 Multi-University Training Contest 10

最新文章

热门文章