公司网站怎么做推广/成品网站1688入口网页版

思路出处

思路：状态表示：dp[i][j]代表a从1——i和b从1 —— j中以b[j]结尾的公共上升子序列的集合； dp[i][j]的值等于该集合的子序列中长度的最大值。首先依据公共子序列中是否包含a[i]，将dp[i][j]所代表的集合划分成两个不重不漏的子集： 不包含a[i]的子集，最大值是dp[i - 1[[j]； 包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b中是哪个数：

    子序列只包含b[j]一个数，长度是1；子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；…子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；

如果直接按上述思路实现，需要三重循环：

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);}}
}

然后我们发现每次循环求得的maxv是满足a[i] > b[k]的dp[i - 1][k] + 1的前缀最大值。 因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。 最终答案枚举子序列结尾取最大值即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=100000000;
const int N=2e6+10;
const int M=1e3+10;
const int inf=0x7f7f7f7f;
const int maxx=2e5+7;ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}ll lcm(ll a,ll b)
{return a*(b/gcd(a,b));
}template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x;
}
template <class T>
void write(T x)
{if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{ll res=1%p;while(b){if(b&1) res=res*a%p;a=1ll*a*a%p;b>>=1;}return res;
}
int a[N],b[N];
int dp[3005][3005];int main()
{SIS;int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++){int mx=1;for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j];if(a[i]==b[j])dp[i][j]=max(mx,dp[i][j]);if(b[j]<a[i])mx=max(mx,dp[i][j]+1);}}int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);cout<<ans<<endl;return 0;
}