MYF

HDU 5087 Revenge of LIS II

Posted on | In | | Visitors

题目链接

HDU 5087

题目类型：DP + DFS

题目来源：BestCoder #16

题目分析

题目大意

最长上升子序列的复仇。

给出n个数，问第二长的上升子序列的长度是多少。

解析

我的做法是，跑一遍O(n2)的LIS，对于位置i，每次回溯到j的时候记录共有多少个值能到达当前DP的最大值dp[i]，然后将它们加入v[i]的vector里，这样就能保证找到所有到达i位置使dp[i]最大的前一个位置的下标。最后跑完之后看最大值是否出现两次，如果出现两次则必然存在另一个序列也能达到mx的长度。否则DFS从最后一位向前回溯最长子序列，看看是否从最后到达最前面只有一条路径，如果回溯到了子序列的第一个位置，那么说明这个能达到这个长度的子序列唯一，否则若有两个位置可以到达该位置，则该长度的子序列必不唯一。

给出几组数据

1
2
3
10
 5
 1 2 2 3 4
 6
 3 1 2 2 3 4
 5
 3 1 2 3 4
 2
 1 1
 4
 1 2 3 4
 5
 1 1 2 2 2
 6
 1 2 2 5 6 3
 3
 3 2 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=1000+50;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn];
vector<int> v[maxn];
int dfs(int x){
    if (v[x].size()==0) {
        return 0;
    }
    if (v[x].size()>1) {
        return 1;
    }
    return dfs(v[x][0]);
}
void work(){
    int n;
    int dp[maxn]={},vis[maxn]={},pre[maxn]={};
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        v[i].clear();
    }
    int len=0,mx=0,pos=-1,now;
    for (int i=1; i<=n; i++) {
        pre[i]=i;
        dp[i]=1;
        for (int j=i-1; j>=1; j--) {
            if (a[j]<a[i]&&dp[i]<dp[j]+1) {
                dp[i]=dp[j]+1;
                v[i].clear();
                v[i].push_back(j);
            }
            else if (a[j]<a[i]&&dp[i]==dp[j]+1){
                v[i].push_back(j);
            }
        }
        if (dp[i]>mx) {
            mx=dp[i];
            now=i;
            pos=-1;
        }
        else if (dp[i]==mx){
            pos=i;
        }
    }
    if (pos!=-1) {
        printf("%d\n",mx);
        return;
    }

    
    if (dfs(now))
        printf("%d\n",max(mx, 1));
    else
        printf("%d\n",max(mx-1, 1));
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        work();
    }
    return 0;
}