P1233木棍加工

系统管理员 2021-10-23 15:12 244阅读 0赞

这个题被算法标签标为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<iostream>
     2 #include<cstdio>
     3 #include<algorithm>
     4 #include<string>
     5 #include<cstring>
     6 #include<cmath>
     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<<len<<endl;
    37     return 0;
    38 }

转载于:https://www.cnblogs.com/china-mjr/p/11278825.html