AcWing 1017. 怪盜基德的滑翔翼
思路：相當于做兩次LIS

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 120;

int t[N];//存數(shù)
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. 攔截導(dǎo)彈（好題）

某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。

但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。

某天，雷達捕捉到敵國的導(dǎo)彈來襲。

由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，導(dǎo)彈數(shù)不超過1000），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。
輸入格式

共一行，輸入導(dǎo)彈依次飛來的高度。
輸出格式

第一行包含一個整數(shù)，表示最多能攔截的導(dǎo)彈數(shù)。

第二行包含一個整數(shù)，表示要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)。
輸入樣例：

389 207 155 300 299 170 158 65

輸出樣例：

6
2

思路：貪心，最優(yōu)方案之一為每次將當前數(shù)放在最小的序列后，做到盡量讓末尾下降得慢

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