洛谷【p1091】合唱队形 树状数组优化求LIS

缘起

继续用树状数组优化LIS. 洛谷【p1091】合唱队形

分析

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
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为
T1,...,Tk, 他们的身高满足峰型, 即
T1<T2<...<Ti>T_{i+1}>...>Tk,   1<=i<K

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
毕竟,音乐老师希望尽可能多的同学参与到大合唱活动中.

【输入】
两行, 第一行是N（2≤N≤100），表示学生的总数.
第二行有n个正整数([130,230]), 表示学生的身高.

【输出】
一个整数——最少需要请几位同学出列

【样例输入】
8
186 186 150 200 160 130 197 220

【样例输出】
4

【限制】
1s

裸的LIS. 令

1
2
3
4
5
状态设计：F[i]表示以i结尾的最长上升子序列，G[i]代表从i开始的最长下降子序列。
状态转移：F[i]=max{F[j+1]}(1<=j < i,A[j]< A[i]),G[i]=max{G[j]+1}(i< j<=n,A[j]< A[i])
边界处理：F[i]=1,G[i]=1(1<=i<=n)
最后的答案是ans=max{F[i]+G[i]-1}(1<=i<=n)
减1的原因是i重复算了两遍

因为本题n较小, 所以完全可以暴力dp, 但是本题刻意练习【1】中给的树状数组优化LIS. 注意, 本题求解的是严格类型的LIS而不是非严格类型的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
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 105;
int n, dpa[maxn], dpb[maxn], ca[maxn], cb[maxn], pa[maxn], pb[maxn],ans, ansa[maxn], ansb[maxn]; // dpa[i](dpb[i])是以a(b)中排名第i的元素结尾的严格单增lis长度,ca(cb)是dpa(dpb)的树状数组,pa[i](pb[i])是a[i](b[i])在原数组中的从小到大的排名

struct kk
{
	int val, idx;
	bool operator<(kk &o)
	{
		return val==o.val?idx<o.idx:val<o.val;
	}
}a[maxn], b[maxn];

void read(int &x)
{
	x = 0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(48+x%10);
}

inline int lowbit(int i)
{
	return i&-i;
}

int querya(int i)
{
	int ret = 0;
	while(i)
	{
		ret = max(ret, ca[i]);
		i-=lowbit(i);
	}
	return ret;
}

int zza(int i)
{
	int lo =0, hi = i, mid, ans=0;
	while(lo<=hi)
	{
		mid = lo+hi>>1;
		if (a[mid].val<a[i].val)
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	return ans;
}

void updataa(int i, int x)
{
	while (i<=n)
	{
		ca[i] = max(ca[i], x);
		i+=lowbit(i);
	}
}

int queryb(int i)
{
	int ret = 0;
	while(i)
	{
		ret = max(ret, cb[i]);
		i-=lowbit(i);
	}
	return ret;
}

int zzb(int i)
{
	int lo =0, hi = i, mid, ans=0;
	while(lo<=hi)
	{
		mid = lo+hi>>1;
		if (b[mid].val<b[i].val)
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	return ans;
}

void updatab(int i, int x)
{
	while (i<=n)
	{
		cb[i] = max(cb[i], x);
		i+=lowbit(i);
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1;i<=n; i++)
	{
		read(a[i].val);
		a[i].idx = i;
		b[n+1-i].val = a[i].val;
		b[n+1-i].idx = n+1-i;
	} // b存储a的逆.
	sort(a+1,a+n+1);
	for (int i = 1;i<=n;i++)
	{
		pa[a[i].idx] = i;
	}
	for (int i = 1;i<=n; i++)
	{
		dpa[pa[i]] = querya(zza(pa[i]))+1;
		updataa(pa[i], dpa[pa[i]]);
	} // 得到dpa
	for (int i = 1;i<=n; i++)
	{
		ansa[a[i].idx] = dpa[i];
	} // ansa[i]存储的是以原先数组a[i]为结尾的元素的严格单增lis长度
	
	sort(b+1,b+n+1);
	for (int i = 1;i<=n;i++)
	{
		pb[b[i].idx] = i;
	}
	for (int i = 1;i<=n; i++)
	{
		dpb[pb[i]] = queryb(zzb(pb[i]))+1;
		updatab(pb[i], dpb[pb[i]]);
	} // 得到dpb
	for (int i = 1;i<=n; i++)
	{
		ansb[b[i].idx] = dpb[i];
	} // ansb[i]存储的是以原先数组b[i]为结尾的元素的严格单增lis长度
	for (int i = 1;i<=n; i++)
	{
		ans = max(ans, ansa[i]+ansb[n+1-i] -1);
	} // ans是峰型序列的最大长度
	write(n-ans);
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1091 合唱队形
评测状态
Accepted
评测分数
100

参考

【1】https://yfsyfs.github.io/2019/10/21/%E6%B4%9B%E8%B0%B7%E3%80%90p1020%E3%80%91%E5%AF%BC%E5%BC%B9%E6%8B%A6%E6%88%AA-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E4%BC%98%E5%8C%96%E6%B1%82LIS/