【二分】AcWing 2978. 最长上升子序列
2021-08-09 18:51:00 # ACM

DP

回顾DP方式求解过程：

$p[i]$：原序列

$dp[i]$：以位置 $i$ 为结尾的最长上升子序列；

$dp_i = \max_{j=1}^{i-1}dp_j+1(p_j<p_i)$

这样显然是 $O(n^2)$ 的；

贪心 + 二分

维护一个数组 $p$，$p_i$ 维护子序列长度为 $i$ 的最小值 

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 100005
	#define MS 100005

int n,m;
int p[MS], tot;

// p[i] 维护子序列长度为 i的最小值 

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		if(!tot || x > p[tot]) p[++tot] = x;
		else{
			int pos = lower_bound(p+1,p+tot+1,x) - p;
			p[pos] = x;
		}
	}
	cout << tot << "\n";
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/

换一种写法

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 2e9
	#define MS 100005

int n,m;
int p[MS], tot;

// p[i] 维护子序列长度为 i的最小值 

void solve(){
	cin >> n;
	int ans = 0;
	for(int i=1;i<=n;i++) p[i] = MAXN; 
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		int pos = lower_bound(p+1,p+n+1,x) - p;
		p[pos] = x;
		ans = max(ans,pos);
	}
	cout << ans << "\n";
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/
Prev
2021-08-09 18:51:00 # ACM
Next