HDU 5904 - LCIS (BestCoder Round #87)

HDU 5904 - LCIS [ DP ]    BestCoder Round #87

题意:

给定两个序列,求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的

分析:

状态转移方程式: dp[a[i]] = max(dp[a[i]], dp[a[i]-1] + 1);

发现其实可以简化为 dp[a[i]] = dp[a[i]-1] + 1;因为计算过程中dp[a[i]]不会降低

对两个序列都求一遍,然后取两者最小值的最大值

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXM = ;
const int MAXN = ;
int t, n, m;
int a[MAXN], b[MAXN];
int dp1[MAXM], dp2[MAXM];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
memset(dp1, , sizeof(dp1));
memset(dp2, , sizeof(dp2));
int top = ;
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
dp1[a[i]] = dp1[a[i]-] + ;
top = max(top, a[i]);
}
for (int i = ; i <= m; i++)
{
scanf("%d", &b[i]);
dp2[b[i]] = dp2[b[i]-] + ;
top = max(top, b[i]);
}
int ans = ;
for (int i = ; i <= top; i++) ans = max(ans, min(dp1[i], dp2[i]));
printf("%d\n", ans);
}
}
上一篇:hdu 4859 海岸线 最小割


下一篇:HDU 4859 海岸线(最大流最小割)