美文网首页
算法提高基础练习打卡(二)

算法提高基础练习打卡(二)

作者: 殇不患_531c | 来源:发表于2020-08-23 18:10 被阅读0次

    AcWing 1017. 怪盗基德的滑翔翼
    思路:相当于做两次LIS

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N = 120;
    
    int t[N];//存数
    int p[N];
    int main(){
    
       int n;
       scanf("%d",&n);
       for(int i=0;i<n;i++){
           
           int temp=0;
           int m;
           scanf("%d",&m);
           for(int j=0;j<m;j++){
               scanf("%d",&t[j]);
           }
           
           //min
           for(int j=0;j<m;j++){
               p[j] = 1;
               for(int s=0;s<j;s++){
                   if(t[s]>t[j]){
                       p[j] = max(p[j],p[s]+1);
                   }
               }
               temp = max(temp,p[j]);
           }
           //max
           for(int j=0;j<m;j++){
               p[j] = 1;
               for(int s=0;s<j;s++){
                   if(t[s]<t[j]){
                       p[j] = max(p[j],p[s]+1);
                   }
               }
               temp = max(temp,p[j]);
           }
           printf("%d\n",temp);
       }
       
       return 0;
    }
    
    1. 登山
      思路:找已一点为尾的up序列,这点为首的up序列(需要两个方向)
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int t;
    int s[1005];
    int m1[1005];
    int m2[1005];
    
    int main(){
        scanf("%d",&t);
        for(int i=0;i<t;i++){
            scanf("%d",&s[i]);
            m1[i] = 1;
            m2[i] = 1;
        }
        
        for(int i=0;i<t;i++){
            for(int j=0;j<i;j++){
                //up
                if(s[j]<s[i]) m1[i] = max(m1[i],m1[j]+1);
                
            }
        }
     //下面这段从后往前,不能合入上面
        for(int i=t-1;i>=0;i--){
            for(int j=t-1;j>i;j--){
                //down
                if(s[j]<s[i]) m2[i] = max(m2[i],m2[j]+1);
            }
        }
        
        
        int r = m1[0]+m2[0]-1;
        for(int i=0;i<t;i++){
            r = max(r,m1[i]+m2[i]-1);
        }
        printf("%d",r);
        
        return 0;
    }
    
    1. 合唱队形
      和上题登山一样

    2. 友好城市

    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    typedef pair<int,int> PII;
    const int N = 5010;
    int r[N],n;
    
    int main(){
        scanf("%d",&n);
        vector<PII> c;
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            c.push_back({a,b});
            r[i] = 1;
        }
        
        sort(c.begin(),c.end());
        
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(c[i].second>c[j].second) r[i] = max(r[i],r[j]+1);   
            }
        }
        
        int re = r[0];
        for(int i=0;i<n;i++){
            re = max(re,r[i]);
        }
        
        printf("%d",re);
        
    }
    
    1. 最大上升子序列和
      就是将计长度换成了计总和

    2. 拦截导弹(好题)

    某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。

    但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。

    某天,雷达捕捉到敌国的导弹来袭。

    由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

    输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
    输入格式

    共一行,输入导弹依次飞来的高度。
    输出格式

    第一行包含一个整数,表示最多能拦截的导弹数。

    第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。
    输入样例:

    389 207 155 300 299 170 158 65

    输出样例:

    6
    2

    思路:贪心,最优方案之一为每次将当前数放在最小的序列后,做到尽量让末尾下降得慢

    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    const int N = 1010;
    int n;
    int a[N],b[N],c[N];
    
    int main(){
        n=0;
        while(cin>>a[n]) n++;
        
        int res = 0;
        for(int i=0;i<n;i++){
            b[i] = 1;
            for(int j=0;j<i;j++){
                if(a[i]<=a[j]) b[i] = max(b[i],b[j]+1);
            }
            res = max(res,b[i]);
        }
        cout<<res<<endl;
        
        int num=0;
        for(int i=0;i<n;i++){
            int cmin=30010;
            int sel;
            bool f = false;
            for(int j=0;j<num;j++){
                if(a[i]<=c[j]&&cmin>c[j]){
                    f = true;
                    cmin = c[j];
                    sel = j;
                }
            }
            if(!f){
                c[num] = a[i];
                num++;
            }else{
                c[sel] = a[i];
            }
        }
        
        cout<<num;
        
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:算法提高基础练习打卡(二)

          本文链接:https://www.haomeiwen.com/subject/alnurktx.html