【笔记】动态规划系列学习之 最长上升子序列(LIS)问题全解

发表于

这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战.

lis - Longest Increasing Subsequence - 最长上升子序列
#1.LIS问题
给定一个序列,找出其中最长的上升子序列,输出长度
###O(nlogn)做法
维护一个集合,第i个元素表示长度为i的上升子序列末尾数字.
每次出现新的数字时,查找并替换它的lower_bound,如果没有则直接插入.
集合长度即为lis长度.
###例题: HDU 1025
排序后求lis,注意roads.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
cpp复制代码pair<int,int> save[M];
int main(void)
{
	int n,kase=0;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
			save[i].first=read(),save[i].second=read();
		sort(save,save+n);
		set<int> st;
		for(int i=0;i<n;i++)
		{
			int val = save[i].second;
			auto it = st.lower_bound(val);
			if(it != st.end()) st.erase(it);
			st.insert(val);
		}	
		printf("Case %d:\nMy king, at most %u road%s can be built.\n\n",
			++kase,st.size(),st.size()==1?"":"s" );
	}
    return 0;
}

#2.LIS问题的变体
1.最初版本:最长上升子序列

1
2
3
4
5
6
7
8
cpp复制代码set<int> st;
for(int i=0;i<n;i++)
{
	int val;
	auto it = st.lower_bound(val);
	if(it != st.end()) st.erase(it);
	st.insert(val);
}

2.最长下降子序列
将原程序中的set<int>改为 set<int,greater<int>>
3.最长不下降子序列
将原程序中的set改为multiset,lower_bound改为upper_bound
4.最长不上升子序列
综合2与3.

例题: HDU 5532

直接求lis(3)与lis(4),判断长度是否都小于n-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
cpp复制代码int save[M];
int main(void)
{
	int t=read();
	while(t--)
	{
		int n=read();
		for(int i=0;i<n;i++) save[i]=read();
		multiset<int> st;
		for(int i=0;i<n;i++)
		{
			int val = save[i];
			auto it = st.upper_bound(val);
			if(it!=st.end()) st.erase(it);
			st.insert(val);
		}
		multiset<int,greater<int>> st2;
		for(int i=0;i<n;i++)
		{
			int val = save[i];
			auto it2 = st2.upper_bound(val);
			if(it2!=st2.end()) st2.erase(it2);
			st2.insert(val);
		}
		printf("%s\n",(int)st.size()>=n-1||(int)st2.size()>=n-1?"YES":"NO" );
	}
	
    return 0;
}

#3.Dilworth定理

Dilworth定理：对于一个有穷偏序集，最少链划分等于最长反链长度。
Dilworth对偶定理：对于一个有穷偏序集，其最少反链划分数等于其最长链的长度。

用人话说,在一个序列中下降子序列的最少个数就等于其最长不下降子序列长度,反过来同理,上升同理,即
lis(1)的长度=lis(4)的个数,
lis(4)的长度=lis(1)的个数,
lis(2)的长度=lis(3)的个数,
lis(3)的长度=lis(2)的个数,
可以简记为,”不”字可以将长度与个数转换.
###例题: luogu P1020 导弹拦截
求lis(4)的长度与个数,即求lis(4)和lis(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
cpp复制代码int save[M];
int main(void)
{
	int n=0;
	while(scanf("%d",&save[n])!=EOF)
		n++;
	multiset<int,greater<int>> st4;
	for(int i=0;i<n;i++)
	{
		int val = save[i];
		auto it = st4.upper_bound(val);
		if(it!=st4.end()) st4.erase(it);
		st4.insert(val);
	}
	set<int> st1;
	for(int i=0;i<n;i++)
	{
		int val = save[i];
		auto it = st1.lower_bound(val);
		if(it!=st1.end()) st1.erase(it);
		st1.insert(val);
	}
	printf("%u\n%u\n",st4.size(),st1.size() );

    return 0;
}

#4.输出答案
给定一个序列,输出LIS长度及LIS.
###O(nlogn)做法
集合中不再维护值,而是维护对应下标,比较规则仍按值比较.
对下标记录一个前驱数组,表示这个下标如果在lis中,它的上一个数是哪个下标.
集合中每插入一个新下标时,这个下标的前驱就是它在集合中上一位的下标.(或者-1)
输出时从集合最后一个元素开始按前驱倒序输出.

###例题: HDU 1160
按速度从大到小排序,求体重的lis.

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
cpp复制代码struct Item{
	int w,s,id;
}save[M];
int cmp_sort(Item a,Item b){
	return a.s==b.s?a.w<b.w:a.s>b.s;
}
struct cmp{
	bool operator()(int a,int b){
		return save[a].w<save[b].w;
	}
};
int last[M];
void print(int a)
{
	if(a==-1) return;
	print(last[a]);
	printf("%d\n",save[a].id );
}
int main(void)
{
	int n=0;
	while(scanf("%d%d",&save[n].w,&save[n].s)!=EOF)
	{
		save[n].id = n+1;
		n++;
	}
	sort(save,save+n,cmp_sort);
	set<int,cmp> st;
	for(int i=0;i<n;i++)
	{
		auto it = st.lower_bound(i);
		if(it != st.end()) st.erase(it);
		it = st.insert(i).first;
		last[i] = (it==st.begin()?-1:*(--it)); 
	}
	printf("%u\n",st.size() );
	print(*st.rbegin());

    return 0;
}

这是一个AC代码,但是可以被hack.
1 4 2 3 3 2 4 1 5 1

#5.记录信息
通过输出答案可以看出,跑一遍lis可以记录很多信息,比如以每个位置为结尾的lis长度.
本质上输出答案也是记录了信息:序列中上一个数的位置.
###Luogu P1091 合唱队形
给一个数字序列,求最少删去几个数能使得序列成为一个先升再降的序列.上升下降部分均可以没有,即lis(1)或lis(2).

跑一遍lis(1),记录以每个位置为结尾的lis长度,记作in.
再倒序跑一遍lis(1),记录以每个位置为结尾的倒序lis长度,记作out.
答案就是maxi=0n−1(n−in[i]−out[i]+1)max_{i=0}^{n-1}(n-in_{[i]}-out_{[i]}+1)maxi=0n−1​(n−in[i]​−out[i]​+1)
out中实际记录的是以每个位置为开头的lis(2)长度.

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
cpp复制代码int save[M];
int in[M],out[M];
struct cmp{
	bool operator() (int a,int b){
		return save[a]<save[b];
	}
};
int main(void)
{
	int n=read();
	for(int i=0;i<n;i++)
		save[i]=read();
	
	set<int,cmp> st;
	for(int i=0;i<n;i++)
	{
		auto it = st.lower_bound(i);
		if(it!=st.end()) st.erase(it);
		it = st.insert(i).first;
		in[i] = it==st.begin()?1:in[*(--it)]+1;
	}
	st.clear();
	for(int i=n-1;i>=0;i--)
	{
		auto it = st.lower_bound(i);
		if(it!=st.end()) st.erase(it);
		it = st.insert(i).first;
		out[i] = it==st.begin()?1:out[*(--it)]+1;
	}

	int ans=n;
	for(int i=0;i<n;i++)
		ans = min(ans,n-in[i]-out[i]+1);
	printf("%d\n",ans );
    return 0;
}

#6. 习题

Luogu P1439

求两个1到n排列的LCS.

映射后求LIS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cpp复制代码int mp[M];
int main(void)
{
	int n=read();
	for(int i=1;i<=n;i++) mp[read()]=i;
	set<int> st;
	for(int i=1;i<=n;i++)
	{
		int val = mp[read()];
		auto it = st.lower_bound(val);
		if(it!=st.end()) st.erase(it);
		st.insert(val);
	}
	printf("%u\n",st.size() );
    return 0;
}

本文也发表于我的 csdn 博客中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%