题目来源
题目难度
3星
算法标签
dp + 优化
参考程序
#include <iostream>
using namespace std;
const int N = 3005;
int n;
int a[N], b[N];
//dp[i][j]表示a的前i个数,b的
//前j个数,并且以b[j]结尾,的最长
//公共上升子序列长度
int dp[N][N];
int main()
{
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 maxv = 1;
for(int j = 1; j <= n; j ++)
{
//不包括a[i]
dp[i][j] = dp[i-1][j];
//包含a[i]
if(a[i] == b[j])
{
dp[i][j] = max(dp[i][j], maxv);
}
//更新maxv:在b[1~j-1]中小于a[i]的所有数的dp[i-1][k]+1的max
if(b[j] < a[i])
{
maxv = max(maxv, dp[i-1][j]+1);
}
}
}
int ans = 0;
for(int j = 1; j <= n; j ++)
{
ans = max(ans, dp[n][j]);
}
cout << ans << endl;
}
标签:int,272,公共,序列,最长,dp
From: https://www.cnblogs.com/chaosliang/p/17201097.html