上海人才网官网站首页,网络 网站,口碑好的网站建设哪家好,有没有电脑做兼职的网站题意#xff1a;
求最长公共上升子序列
题解#xff1a;
最长公共上升子序列 最长公共子序列#xff08;LCS#xff09;与最长上升子序列#xff08;LIS#xff09; LCS核心代码#xff1a; for(int i1;in;i){for(int j1;jm;j){if(a[i]b[j])dp[i][j]max(dp[…题意
求最长公共上升子序列
题解
最长公共上升子序列 最长公共子序列LCS与最长上升子序列LIS LCS核心代码 for(int i1;in;i){for(int j1;jm;j){if(a[i]b[j])dp[i][j]max(dp[i][j],dp[i-1][j-1]1);else dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}LIS核心代码 for(int i1;in;i){dp[i]1;for(int j1;ji;j){if(a[j]a[i])dp[i]max(dp[i],dp[j]1);}mxmax(mx,dp[i]);}最长公共上升子序列的代码就是在最长公共子序列上找一遍最长上升子序列即可。也就是在判断a[i] b[j]的前提下再求出上升序列 f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合 f[i][j]的值等于该集合的子序列中长度的最大值 复杂度O(n3) 代码
for (int i 1; i n; i )
{for (int j 1; j n; j ){f[i][j] f[i - 1][j];if (a[i] b[j]){int maxv 1;for (int k 1; k j; k )if (a[i] b[k])maxv max(maxv, f[i - 1][k] 1);f[i][j] max(f[i][j], maxv);}}
}我们仔细看看代码第三层for循环是用来求之前的小于a[i]的最长公共上升子序列1长度实际上我们需要知道的只有之前的最长公共上升子序列的长度这样一来我们可以用一个变量val来存放 F[ i-1 ][ k ] 中的最大值从而就可以省略第三层循环
for (int i 1; i n; i ){int maxv 1;for (int j 1; j n; j ){f[i][j] f[i - 1][j];if (a[i] b[j]) f[i][j] max(f[i][j], maxv);if (a[i] b[j]) maxv max(maxv, f[i - 1][j] 1);}}我们还可以将维度缩到一维 可知f[i][j]都是由f[i-1][j]得来的 我们用f[i]表示a序列前i个元素与b序列的LCIS长度t为最长LCIS的结尾元素位置新的转移方程 f[i] f[t] 1 (a[i] b[j]) 这样就降到一维
for(int i1;in;i){maxx0;for(int j1;jn;j){if(b[j]a[i]maxxf[j]) maxxf[j];if(b[j]a[i]) f[j]maxx1;}}代码
二维空间的代码
#include cstdio
#include iostream
#include algorithmusing namespace std;const int N 3010;int n;
int a[N], b[N];
int f[N][N];int main()
{scanf(%d, n);for (int i 1; i n; i ) scanf(%d, a[i]);for (int i 1; i n; i ) scanf(%d, b[i]);for (int i 1; i n; i ){int maxv 1;for (int j 1; j n; j ){f[i][j] f[i - 1][j];if (a[i] b[j]) f[i][j] max(f[i][j], maxv);if (a[i] b[j]) maxv max(maxv, f[i - 1][j] 1);}}int res 0;for (int i 1; i n; i ) res max(res, f[n][i]);printf(%d\n, res);return 0;
}一维数组的代码
#includeiostream
#includecstdio
#includecstring
#includecmath
#includecstdlib
#includealgorithm
#includestring
#define ll long long
#define maxn 3050
#define inf 2147483647
#define mod 10003
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std;
inline int read(){int x0,f1; char chgetchar();while(!isdigit(ch)) {if(ch-)f-1;chgetchar();}while(isdigit(ch)) {xx*10ch-48;chgetchar();}return x*f;
}
int n,a[maxn],b[maxn],f[maxn],maxx;
signed main(){nread();for(int i1;in;i) a[i]read();for(int i1;in;i) b[i]read();for(int i1;in;i){maxx0;for(int j1;jn;j){if(b[j]a[i]maxxf[j]) maxxf[j];if(b[j]a[i]) f[j]maxx1;}}maxx0;for(int i1;in;i) if(maxxf[i]) maxxf[i];printf(%d,maxx);return 0;
}
