一.最简单的最长上升子序列
AcWing 895. 最长上升子序列
这是一道典型的dp例题， dp的两个重要元素：状态表示和状态计算。其中维度的选择是很关键的，要求既能够表示出转移过程中的状态，而且能够计算出结果，在此基础上，要求维度尽可能小。
我们这里可以用dp[i]来表示以第i个数结尾的数值上升的子序列的集合，属性是max；那么对于状态转移的话，我们可以这样考虑：每一个上升子序列以倒数第二个数选什么来分类。可以有以下情况，dp[i-1]=0（即当前是第一个数），a[k] (k=0,1,……i-1); 要注意这里面并不是每一个状态都存在，我们只需要把存在的状态进行转移就可。
状态转移方程还是很好推的，我们记这个状态可以由上一个状态 j 转移过来，那么本状态的max就等于 j 状态的max+1（本次状态的长度） 。如下：
dp[i]=dp[j]+1;
结合上面两部分，整个转移方程也很容易写出来啦
for(int j=1;j<i;j++) if(a[j]<a[i]) //保证是上升子序列 dp[i]=max(dp[i],dp[j]+1);
最后，一定要记得给dp赋初值呀！
完整代码如下：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; ll dp[maxn],n,a[maxn]; int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j<i;j++) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1); } ll res=-1; for(int i=1;i<=n;i++) res=max(res,dp[i]); cout<<res<<endl; return 0; }
二： 单调队列优化的最长上升子序列
朴素版本的我们已经写完了，接下来就是考虑优化的问题了。感觉优化时有点贪心的思想。
举个栗子~
就拿本题的样例吧~
3 1 2 1 8 6 6
根据我们在“一”中的思想，dp[i]表示 (balabala)(忘记了的回去看一下~)
其实很容易能够知道，开始的时候，长度为1的上升子序列有两个：{3} ， {1} 如果一个数能接到3的后面，也就能接到1的后面~对，就是这样！那么既然这样的话，第一个子序列就没有存在的意义啦（好残忍）。 因为接到1的后面更优。
简单总结就是，对于每一组相同长度的上升子序列，我们可以只记录a[i]最小的那一组，保证最优解和高效性。
同样的，我们存储一下不同长度下最小的结尾值，我们会发现结尾值和长度是正相关的。基于此性质，可以用单调队列来优化此dp。
假如数组f现在存了数，当到了数组a的第i个位置时，首先判断a[i] > f[cnt] ？ 若是大于则直接将这个数添加到数组f中，即f[++cnt] = a[i];这个操作时显然的。
当a[i] <= f[cnt] 的时,我们就用a[i]去替代数组f中的第一个大于等于a[i]的数，因为在整个过程中我们维护的数组f 是一个递增的数组，所以我们可以用二分查找在 logn 的时间复杂的的情况下直接找到对应的位置，然后替换，即f[l] = a[i]。
好了代码如下
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int q[maxn],a[maxn],n,cnt; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int find(int x){ int l=1,r=cnt; while(l<r){ int mid=l+r>>1; if(q[mid]>=x) r=mid; else l=mid+1; } return l; } int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); q[++cnt]=a[1]; for(int i=2;i<=n;i++){ if(a[i]>q[cnt]) q[++cnt]=a[i]; else{ int temp=find(a[i]); q[temp]=a[i]; } } printf("%d\n",cnt); return 0; }
三.题目
欢迎来玩~
思路： 当确定完起点后，就转化成了在两个方向上分别求解LIS问题；
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=110; int a[maxn],dp[maxn]; int main(){ int t;cin>>t; while(t--){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; memset(dp,0,sizeof dp); int res=-1; for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j<i;j++) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1); res=max(res,dp[i]); } for(int i=n;i>=1;i--){ dp[i]=1; for(int j=n;j>i;j--) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1); res=max(res,dp[i]); } cout<<res<<endl; } return 0; }
1014. 登山 - AcWing题库
思路：
本题有三个要求：1.每次所浏览景点的编号都要大于前一个浏览景点的编号。
2.不连续浏览海拔相同的两个景点
3.一旦开始下山，就不再向上走了
分析这三个要求：可以得出最后得到的子序列是先上升再下降的，那么我们可以根据峰值来进行计算。记左边的以a[k]结尾的最长上升子序列长度 max = l [ k ] , 右边的以a[k] 开始的最长下降子序列长度 max = r [ k ] , 那么可得到
dp[k]=l[k]+r[k]-1; //要除去本身
代码：
一定要记得初始化！
#include<bits/stdc++.h> using namespace std; const int maxn=1100; int a[maxn],l[maxn],r[maxn]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ l[i]=1; for(int j=1;j<i;j++) if(a[j]<a[i]) l[i]=max(l[i],l[j]+1); } for(int i=n;i>=1;i--){ r[i]=1; for(int j=n;j>i;j--) if(a[j]<a[i]) r[i]=max(r[i],r[j]+1); } int res=-1; for(int i=1;i<=n;i++) res=max(res,l[i]+r[i]-1); cout<<res<<endl; return 0; }
思路： 跟上题思路相同，只需最后输出总数减去最大值即可
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1100; int a[maxn],l[maxn],r[maxn]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ l[i]=1; for(int j=1;j<i;j++) if(a[j]<a[i]) l[i]=max(l[i],l[j]+1); } for(int i=n;i>=1;i--){ r[i]=1; for(int j=n;j>i;j--) if(a[j]<a[i]) r[i]=max(r[i],r[j]+1); } int res=-1; for(int i=1;i<=n;i++) res=max(res,l[i]+r[i]-1); cout<<n-res<<endl; return 0; }
1012. 友好城市 - AcWing题库
思路： 我们把北岸排好序之后会有a[i1].n<a[i2].n,(i1<i2)a[i1].n<a[i2].n,(i1<i2)；假如对于i1,i2i1,i2,它们的南岸坐标 a[i1].s<a[i2].sa[i1].s<a[i2].s ，那么就会有交叉，而所有城市的友好城市不相同，所以我们应该建造一个严格上升的子序列。（摘自大佬博客）
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=5100; struct node{ int x,y; }a[maxn]; int dp[maxn],n; bool cmp(node a,node b){ return a.x<b.x; } int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y; sort(a,a+n,cmp); int res=-1; for(int i=0;i<n;i++){ dp[i]=1; for(int j=0;j<i;j++) if(a[i].y>a[j].y) dp[i]=max(dp[i],dp[j]+1); res=max(res,dp[i]); } cout<<res<<endl; return 0; }
思路： 跟LIS类似的，只不过初始化要变为a[i]，转移方程为
dp[i]=max(dp[i],dp[j]+a[i]);
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1100; int a[maxn],dp[maxn]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int res=-1; for(int i=1;i<=n;i++){ dp[i]=a[i]; for(int j=1;j<i;j++) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]); res=max(res,dp[i]); } cout<<res<<endl; return 0; }
待补：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n,h[maxn],dp[maxn],q[maxn]; int main(){ int x; while(cin>>h[n]) n++; int res=0,cnt=0; for(int i=0;i<n;i++){ dp[i]=1; for(int j=0;j<i;j++) if(h[i]<=h[j]) dp[i]=max(dp[i],dp[j]+1); res=max(res,dp[i]); } cout<<res<<" "; /**贪心：从前往后扫描每个数，对于每个数 情况一：如果现有的子序列的结尾都小于当前数 则创建新的子序列 情况二：将当前数放到结尾大于等于他的最小子序列后 **/ for(int i=0;i<n;i++){ int k=0; while(k<cnt&&q[k]<h[i]) k++; q[k]=h[i]; if(k>=cnt) cnt++; } cout<<cnt<<endl; return 0; }
#include<bits/stdc++.h> #define Cutele main using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=1100; char a[maxn],b[maxn]; int dp[maxn][maxn],n,m; int Cutele(){ scanf("%d%d",&n,&m); scanf("%s%s",a+1,b+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); } printf("%d\n",dp[n][m]); return 0; }
