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

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;
}

1014. 登山
      思路：找已一点为尾的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;
}

482. 合唱队形
     和上题登山一样

483. 友好城市

#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);
    
}

1016. 最大上升子序列和
      就是将计长度换成了计总和

1017. 拦截导弹（好题）

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

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

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

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

输入导弹依次飞来的高度（雷达给出的高度数据是不大于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;
}