寒假集训 Day2 F Wooden Sticks HDU1051:木条排序

1.12F题 HDU-1051

题目大意:

n个具有l、w权值的木条，找出尽可能多的上升至序列，木条 i 比木条 j 大当且仅当 li > lj 并且 wi > wj时。

Sample Input
3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1
Sample Output
2
1
3

解题思路：

1.开始的时候我想对所有的木条进行l 、w的拓扑排序， 然后找到极小的木条便加1，知道所有木条都用完。但是在如图排序下会有bug。

2.讲解的正确解题思路：对l排序，这样整个序列满足l≤l​′，然后遍历这个序列，如果还满足w≤w​′​​，把这个木棍的下标记下来，去找下一个满足条件的木棍，这样找下去就找到第一个子序列。再去找剩下的，发现我们不知道哪些是找过的，可以给木棍加一个 used 状态，0 为未访问，1 为访问过，每次找子序列先找到一个未访问过的木棍，把 res 加 1 ，然后对于这个序列我贪心的去找下一根木棍并把它的 used 记为 1 。全部木棍被标为 1 的时候也就找完了。

AC代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
#include<algorithm>
#include<limits.h>
#define rep(i,l,p) for(int i=l; i<=p; i++)
#define drep(i,p,l) for(int i=p; i>=l; i--)
using namespace std;
const int maxN = 5005;
typedef pair<int, int> P;
int n;
int T;
bool used[maxN]; 
P wood[maxN];
int main(){
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);

    scanf("%d",&T);
    rep(z,1,T){
        scanf("%d",&n);
        fill(used,used+maxN,false);
        rep(i,1,n){
            scanf("%d%d",&wood[i].first,&wood[i].second);
        }

        sort(wood+1,wood+1+n);

        int ans = 0;
        int usednum = 0;
        while(usednum < n){
            ans++;
            int w = INT_MIN; 
            rep(i,1,n){
                if ( used[i] ) continue;
                if ( wood[i].second >= w ){
                    w = wood[i].second;
                    used[i] = true; 
                    usednum++;
                } 
            }
        }

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

    }   
    return 0;
}