# lIS
全名longest increasing subsequence,最長遞增子序列
### 1.Robinson-Schensted-Knuth Algorithm
概念:以greedy為基礎,二元搜尋加速
1. 初始作業
```cpp=
//測資: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回傳元素的淺能還大)
```cpp=
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
```cpp=
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了
```cpp=
reverse(ans.begin(),ans.end());
for(auto i:ans){
cout << i << " ";
}
```
#非嚴格遞增子序列要使用upper_bound#
說明:因為同為value的值可以出現很多次,所以要找大於value中最小的值來替換
```cpp=
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;
}
}
```
另一種寫法
```cpp=
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>
```cpp=
#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:
```cpp=
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]裡面
```cpp=
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]
```cpp=
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 :
```cpp=
#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;
}
```
Sign in with Wallet
Connect another wallet