# lIS

全名longest increasing subsequence,最長遞增子序列

### 1.Robinson-Schensted-Knuth Algorithm
概念:以greedy為基礎,二元搜尋加速

1. 初始作業

//測資:a[]
vector<int> stk{a[0]},len(a.size());
//先放入一個數避免取stk.back()時segmentation fault
len[0]=1;

2. 遍歷一次a,如果該元素大於stk.back()的話就放入尾端
否則就用lower_bound找到第一個大於或等於該元素的元素,並把他替換掉(該元素成為lis的淺能比lower_bound回傳元素的淺能還大)

for(int i=1;i<a.size();i++){
    if(a[i]>stk.back()){
        stk.push_back(a[i]);
        len[i]=stk.size();
    }else{
        auto it=lower_bound(stk.begin(),stk.end(),a[i]);
        *it=a[i];
        len[i]=it-stk.begin()+1;
    }
}

3. 從尾開始到回去找,因為這樣才能找到成為lis淺能最大的,先設一個變數=LIS,接著從len的最後倒回去找如果len[i]==now,就代表在做LIS時有放進一個元素a[i],該元素屬於LIS,所以要把他加到ans

vector<int> ans;
    int now=stk.size();
    for(int i=a.size()-1;i>=0;i--){
        if(len[i]==now){
            ans.push_back(a[i]);
            now--;
        }
    }
}

4. 最後顛倒過來就是正的LIS了

reverse(ans.begin(),ans.end());
for(auto i:ans){
    cout << i << " ";
}

#非嚴格遞增子序列要使用upper_bound#

說明:因為同為value的值可以出現很多次,所以要找大於value中最小的值來替換

for(int i=1;i<testlen;i++){
    if(test[i]>dparr.back()){
        dparr.push_back(test[i]);
        lislen++;
        dp[i]=lislen;
    }else{
        auto it=upper_bound(dparr.begin(),dparr.end(),test[i]);
        *it=test[i];
        dp[i]=it-dparr.begin()+1;
    }
}

另一種寫法

for(int i=0;i<testlen;i++){
    int value=test[i];
    int len=upper_bound(dparr.begin(),dparr.end(),value)-dparr.begin();
    if(len==aparr.size()){  //找不到
        dparr.push_back(value);
    }else{
        test[len]=value;
    }
}

<a href="https://zerojudge.tw/ShowProblem?problemid=d242">ZJ d242: 00481 - What Goes Up</a>

#include <bits/stdc++.h>
using namespace std;

int main(){
  int x;
  vector<int> a;
  while(cin >> x) a.push_back(x);
  vector<int> stk{a[0]},len(a.size());
  len[0]=1;
  
  for(int i=1;i<a.size();i++){
    if(a[i]>stk.back()){
      stk.push_back(a[i]);
      len[i]=stk.size();
    }else{
      auto it=lower_bound(stk.begin(),stk.end(),a[i]);
      *it=a[i];
      len[i]=it-stk.begin()+1;
    }
  }
  
  cout << stk.size() << '\n' << "-" << '\n';
  
  vector<int> ans;
  int now=stk.size();
  for(int i=a.size()-1;i>=0;i--){
    if(len[i]==now){
      ans.push_back(a[i]);
      now--;
    }
  }
  
  for(int i=ans.size()-1;i>=0;i--){
    cout << ans[i] << '\n';
  }
  return 0;
}

### 2.Dynamic Programming

看當前元素有沒有比前面的元素小,有的話,代表LIS可以變長,就把LIS更新到當前的陣列裡

DP狀態轉移:

if(dp[j]<dp[i])
    dp[i]=max(dp[i],dp[j]+1) for j in range(0,i-1);

Code:

int getlcs(vector<int> &nums){
    int n=nums.size();
    vector<int> lis(n,1);  //每個LIS初始都是自己一個

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){  //如果當前元素nums[i]有大於前面的任何一個元素nums[j]
                lis[i]=max(lis[i],lis[j]+1);  //那就更新到lis[i]=前面元素nums[j]的lis+1
            }
        }
        ans=max(ans,lis[i]);  //更新最大值
    }
    return ans;
}

題目:<a href="https://zerojudge.tw/ShowProblem?problemid=c115">c115: 00437 - The Tower of Babylon</a>

Solution 1:看前面有沒有長寬都比我小的,如果有代表可以疊上去,就把答案更新到lis[i]裡面

vector<int> lis(n*3,0);
int ans=0;
for(int i=0;i<n*3;i++){
    lis[i]=arr[i].h;  //初始化,每個lis都是自己
    for(int j=0;j<i;j++){
        if(arr[i].x<arr[j].x && arr[i].y<arr[j].y){
            lis[i]=max(lis[i],lis[j]+arr[i].h);
        }
    }
    ans=max(ans,lis[i]);
}

suoution 2:看我後面有沒有長寬都比我小的,如果有代表後面那個方塊可以疊加到當前方塊身上,就把當前的高度更新到lis[j]

vector<int> lis(n*3,0);
int ans=0;
for(int i=0;i<n*3;i++){
    lis[i]+=arr[i].h;  //把前面最高的高度加上自己的高度就是當前最高的高度
    for(int j=i+1;j<n*3;j++){
        if(arr[i].x>arr[j].x && arr[i].y>arr[j].y){
            lis[j]=max(lis[i],lis[j]);
        }
    }
    ans=max(ans,lis[i]);
}

Code :

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x,y,h;
};

bool cmp(node a,node b){
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}

int main(){
    int n,a,b,c,casen=1;
    while(cin >> n && n){
        vector<node> arr(n*3);
        for(int i=0;i<n;i++){
            cin >> a >> b >> c;
            arr.push_back({max(a,b),min(a,b),c});
            arr.push_back({max(a,c),min(a,c),b});
            arr.push_back({max(b,c),min(b,c),a});
        }
        sort(arr.begin(),arr.end(),cmp);
        
        vector<int> lis(n*3,0);
        int ans=0;
        for(int i=0;i<n*3;i++){
            lis[i]+=arr[i].h;
            for(int j=i+1;j<n*3;j++){
                if(arr[i].x>arr[j].x && arr[i].y>arr[j].y){
                    lis[j]=max(lis[i],lis[j]);
                }
            }
            ans=max(ans,lis[i]);
        }
        cout << "Case " << casen++ <<": maximum height = " << ans << '\n';
    }
    return 0;
}