By yusijia

Updated:

Contents
  1. 1. 百练 2757

百练 2757

  • 三种方法：
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

//最长上升子序列的长度

方法一：
定义状态：dp[i]为以num[i]为最大值最长上升子序列的长度
状态转移方程：dp[i] = max(dp[i], dp[j] + 1);


#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int num[1010];
int dp[1010];

int solve(int n)
{
    int i, j, maxs;
    for(i = 1; i <= n; i++)//初始化为1
        dp[i] = 1;
    for(i = 2; i <= n; i++){
        for(j = 1; j < i; j++){
            if(num[j] < num[i]) 
                dp[i] = max(dp[j] + 1, dp[i]);
        }
    }
    maxs = dp[1];
    for(i = 2; i <= n; i++)//找最长上升子序列
        if(maxs < dp[i])
            maxs = dp[i];
    return maxs;
}

int main()
{
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d", &num[i]);
        }
        printf("%d\n", solve(n));
    }
    return 0;
}

//////////////////////////////////////////


方法二：

// d 数组存当前长度时最长的上升序列的长度,然后再输入数据时就去和数组对一下，
看看有没有满足条件的更小的数据，如果有更新他，如果更新到后面j>ans了，就增加
最长的上升序列的长度

//可以在每次超过ans时记录一下数组，从而保存最长上升子序列

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
using namespace std;

int d[1010];
// int date[1010];

int main()
{
    int a, n, i, j, ans = 0;
    while(scanf("%d", &n) != EOF){
        memset(d, 0x7f, sizeof(d));	//初始化为很大的数
	//memset(date, 0, sizeof(date));
        for(i = 0; i < n; i++){
            scanf("%d", &a);
            for(j = 1; d[j] < a; j++)  
                ;   //注意这里有个分号
            d[j] = a;
	    if(j > ans){
                ans = j;
		/*for(int k = 1; k <= ans; k++)
                    date[k] = d[k];*/
	    }
        }
        printf("%d\n", ans);
	/*for(int k = 1; k <= ans; k++)
            printf("%d ", date[k]);*/
    }
    return 0;
}

///////////////////////////////////////////

方法三：

#include <cstdio>
#include <cstring>
#define INF 0x7f7f7f7f

int dp[1005];

int binary_find(int n, int a)
{
    int l = 0, r = n - 1, m;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (dp[m] > a)
            r = m - 1;
        else if (dp[m] < a)
            l = m + 1;
        else
            return m;
    }
    return l;
}
int main()
{
    int n, a, ans, j;
    while (scanf("%d", &n) != EOF)
    {
        memset(dp, INF, sizeof(dp));
        ans = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &a);
            j = binary_find(ans, a);
            if (j >= ans)
                ans = j + 1;
            dp[j] = a;
        }
        printf("%d\n", ans);
    }
    return 0;
}
Contents
  1. 1. 百练 2757