closefrom

P1233 木棍加工

贪心。
先将长度排序，再依次寻找宽度不上升序列，将它们全部标记，最后寻找没有被标记的。

//My AC Code
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
bool f[5005];
struct node{
    int l,w;
}nn[5005];
bool cp(node a,node b){if(a.l==b.l)return a.w>b.w;else return a.l>b.l;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&nn[i].l,&nn[i].w);
    sort(nn+1,nn+n+1,cp);
    int pd=0,sum=0;
    for(int i=1;i<=n;i++){
        if(!f[i]){
            pd=nn[i].w;
            for(int j=i+1;j<=n;j++){
                if(!f[j]&&pd>=nn[j].w){
                    pd=nn[j].w;
                    f[j]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)if(!f[i])sum++;
    printf("%d",sum);
    return 0;
}