【算法】dp题单

题单链接： https://vjudge.net/contest/574209#overview

目录

1. 洛谷 P1020 导弹拦截 （dp+二分+Dilworth 定理）

2. P1439 最长公共子序列（二分求最长公共子序列）

3. 洛谷 P1854 花店橱窗布置 （线性dp + 用pre数组记录路径） 

---

1. 洛谷 P1020 导弹拦截 （dp+二分+Dilworth 定理）

题目：  https://www.luogu.com.cn/problem/P1020

思想：第一问是求最长不上升子序列，即后一项小于等于前一项，由于数据1e5，考虑二分。

首先把当前项小于等于前一项的加入 f 数组，如果当前项大于 f 数组前一项，那么向前找 f 数组的第一项小于当前项的下标，并用当前值代替二分找到的这个数。

第二问是求不上升子序列的个数，根据Dilworth 定理，一个序列若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数，可以知这题求最长上升子序列的个数。首先把当前值大于 f 数组前一项的值加入 f 数组。如果小等于，那么找到 f 数组第一个大于等于当前值的项（为什么是大于等于，而不是大于，因为最长上升子序列要满足严格大于，所以等于的情况也需要被替代），并用当前值代替二分找到的这个值。

考虑一个数列5 2 3 1 4

首先，把5加入答案序列中，然后加2，发现2<5所以显然2替换5不会使结果更差，

那么答案序列就是{2},然后加3，发现3>2，所以直接把3加到答案序列中：{2,3}

然后加1，我们发现1<3，于是我们找到一个最小的但是比1大的数字2，然后把1替换2，为什么这么做不会影响结果呢？你可以这么想，我们当前已经求出了一个当前最优的序列，如果我们用1替换2，然后后面来一个数字替换了3，那么我们就可以得到一个更优的序列，而如果没有数字替换3，那么这个1替换2也就是没有贡献的，不会影响我们结果的最优性。至于，如何找到一个最小的但是大于某个数字的数字，弄个二分查找就行了，因为我们的答案序列是有序的呀。

代码：

// Problem: B - 导弹拦截
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/B
// Memory Limit: 131 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e5+5;
const int inf = 0x3f3f3f3f;int a[N];
int f[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int x=0;int n=0;while(cin>>x){   a[++n]=x;}memset(f,0,sizeof(f));f[0]=1e9;  int cnt=0;  for(int i=1;i<=n;i++){if(a[i]<=f[cnt]){   //得到不递增的数组f[++cnt]=a[i];  }else{  int l=1,r=cnt;  //找到第一个小于当前导弹高度的元素位置，将其更新为导弹高度while(l<r){int mid=(l+r)/2;if(f[mid]<a[i]){r=mid;}else l=mid+1;}f[l]=a[i];}/*for(int i=1;i<=cnt;i++){cout<<f[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";cnt=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){if(a[i]>f[cnt]){  //找到递增数组f[++cnt]=a[i];}else{int l=1,r=cnt;while(l<r){  //找到第一个大于等于当前导弹高度的导弹位置，将其更新为导弹高度int mid=(l+r)/2;if(f[mid]>=a[i]){r=mid;}else l=mid+1;}f[l]=a[i];}/*for(int i=1;i<=cnt;i++){cout<<f[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";return 0;	}

 

2. P1439 最长公共子序列（二分求最长公共子序列）

 题目：  https://www.luogu.com.cn/problem/P1439

思想：

首先，我们可以想到，最长公共子序列，就是两段所含数字完全一样，并且数字的顺序也是完全一样的序列。

而顺序，我们可以想到类似哈希的思想，考虑建立一个类似map的关系数组f[ai]=i，那么我们找到的序列只要是上升的，顺序就是一样的，然后考虑数字完全一样，由于我们已经有了一个f[ai]=i,所以我们把对应的bi改成f[bi]，就可以确保数字相等了呀！

这时，就是在f[bi]的数组中求个最长上升子序列了，二分搞一搞就好了。STL大法好！

代码：

// Problem: C - 最长公共子序列
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/C
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e5+5;
const int inf = 0x3f3f3f3f;int n;
int a[N],b[N];
int f[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=i;}for(int i=1;i<=n;i++){cin>>b[i];//cout<<mp[b[i]]<<' ';}//cout<<"\n";//mp[b[i]]可以表示a数组中的每个数在b中的位置保证数字一样//然后找最长上升子序列保证顺序一样memset(f,127,sizeof(f));f[0]=0;int cnt=0;for(int i=1;i<=n;i++){if(mp[b[i]]>f[cnt]){  //找到b数组的最长上升子序列f[++cnt]=mp[b[i]];}else{int l=0,r=cnt;while(l<r){int mid=(l+r)/2;if(f[mid]>mp[b[i]]){r=mid;}else l=mid+1;}f[l]=min(mp[b[i]],f[l]);}/*for(int i=1;i<=cnt;i++){cout<<mp[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";return 0;	}

 

3. 洛谷 P1854 花店橱窗布置 （线性dp + 用pre数组记录路径） 

 题目：  https://www.luogu.com.cn/problem/P1854

思想：用 k 遍历 j 找到这一行最大的值，并且用 pre 数组记录当前点前一个位置为 k ，即上一行最大值的位置，结果最大值需要遍历最后一行每一列的值，而不是 f[n][m]，然后以这个点往前找

pre数组 ，用pos数组存下每一行的值，最后输出。 pos[i-1] = pre[i][pos[i]]

代码：

// Problem: E - 花店橱窗布置
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/E
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 1001;
const int inf = 0x3f3f3f3f;int n,m;
int a[N][N];
int f[N][N];
int pre[N][N];
int pos[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=-inf;}}memset(pre,0,sizeof(pre));/*for(int i=1;i<=n;i++){f[0][i]=0;}*/for(int i=1;i<=n;i++){f[0][i]=0;for(int j=i;j<=m;j++){for(int k=i-1;k<j;k++){if(f[i-1][k]+a[i][j]>f[i][j]){f[i][j]=f[i-1][k]+a[i][j];pre[i][j]=k;}}}}int maxv=-inf;for(int i=1;i<=m;i++){if(f[n][i]>maxv){pos[n]=i;maxv=f[n][i];}}cout<<maxv<<"\n";for(int i=n;pre[i][pos[i]]!=0;i--){pos[i-1]=pre[i][pos[i]];}for(int i=1;i<=n;i++){cout<<pos[i]<<' ';}cout<<"\n";return 0;	}