这个题被算法标签标为DP，但其实可能只是用dp求子序列，，（n方）

给出l与w,只要是l与w同时满足小于一个l与w，那么这个木棍不需要时间，反之需要1.看到这个题，首先想到了二维背包，然后发现没有最大的容量，放弃。然后又联想到了活动选择，来一个结构体排序和贪心，但是发现贪心其实具有后效性放弃。然后看了题解，发现最长不下降子序列是正解！碰巧昨天学习了中科大少年班lhw大佬发在群里的..序列,所以便去思考了。先用结构体存下l与w，然后排序l。再用nlogn的算法去求解最长不下降子序列，长度则代表时间。因为l已经从大到小排序好了，只要宽度是上升（>)的就代表时间必须存在，len++,如果是下降的，就去替换，时间保持不变。这类似于导弹拦截。另外，洛谷这个题的数据有错误。亲测输入数据反了。

1.把典型题迁移运用到复杂题中，总可以找到摸板的，关键在于弄懂会写简单题，那天远足回来写的导弹拦截，效果并不好

2.贪心是可以尝试的

3.upper（lower）_bound一定要运用起来

代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define N 100001 8 using namespace std; 9 struct node{10 int l;11 int w;12 }a[N];13 bool cmp(node a,node b){14 return a.l> b.l;15 }16 int n;17 int b[N];18 int ans=1;19 int len=1;20 int main(){21 scanf("%d",&n);22 for(int i=1;i<=n;i++){23 cin>>a[i].l>>a[i].w;24 } 25 sort(a+1,a+n+1,cmp);26 b[1]=a[1].w;27 for(int i=1;i<=n;i++){28 if(a[i].w>b[len]){29 b[++len]=a[i].w;30 }31 else{32 int j=lower_bound(b+1,b+len+1,a[i].w)-b;//找到第一个大于等于他的 33 b[j]=a[i].w;34 }35 }36 cout<
           
            <