BestCoder16 1002.Revenge of LIS II(hdu 5087) 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5087

题目意思:找出第二个最长递增子序列,输出长度。就是说,假如序列为 1 1 2,第二长递增子序列是1 2(下标为2 3),而第一长递增子序列也是(下标为 1 3)。

我一开始天真的以为,还是利用求最长递增子序列的算法啦,第二长不就是对dp 数组sort完后(从小到大)的dp[cnt-1] 啦,接着就呵呵啦~~~~= =

题解说,要加多一个 dp 数组,以便对当前下标值为 i 的数 a[i] 为结尾求出第二条dp序列,如果长度一样就直接那个长度了,否则是长度减 1。一直对每个数这样处理,处理到序列最后一个数就是答案了。

以下是看别人的。设 dp[i][0] 表示以a[i]这个数为结尾的最长递增子序列的长度,dp[i][1] 表示以a[i]这个数为结尾的第二长递增子序列的长度(可能为dp[i][0],也可能是dp[i][0]-1)

然后把每个数的两个dp值放进ans数组中,sort之后,答案就为ans[cnt-2]。

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int N = + ; int a[N], ans[*N];
int dp[N][]; int main()
{
int T, n;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
while (scanf("%d", &T) != EOF)
{
while (T--)
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
memset(dp, , sizeof(dp));
int cnt = ;
for (int i = ; i <= n; i++)
{
dp[i][] = ;
for (int j = ; j < i; j++)
{
if (a[j] < a[i])
{
int x = dp[j][] + ;
int y = dp[j][] + ; if (x > dp[i][])
swap(x, dp[i][]);
dp[i][] = max(x, dp[i][]);
dp[i][] = max(y, dp[i][]);
}
}
ans[cnt++] = dp[i][];
ans[cnt++] = dp[i][];
}
sort(ans, ans+cnt);
printf("%d\n", ans[cnt-]);
}
}
return ;
}
上一篇:BestCoder20 1002.lines (hdu 5124) 解题报告


下一篇:MIPI DSI协议介绍