BZOJ 3831 Little Bird

发表于 | 更新于

Link

233居然没有想出单调队列的做法 觉得用线段树妥妥T飞，单调队列没法维护 再一次被教育了

Solution

f[i]=min{f[j]+(h[j]≤h[i])∣j+k≤i}f[i]=\min\left\{f[j]+(h[j]\le h[i])|j+k\le i\right\} 如果是f[j]f[j]加一个常数，显然维护一个f[]f[]递增的单调队列 加的不是常数，但也可以看到加的数字非00即11。也就说，原本有f[u]<f[v]f[u]< f[v]，转移过来的DP值uu至少不会比vv大。 所以按照这个结论就可以维护了 DP值不相同，按照DP值从小到大排序 否则，按照高度从大到小排序

Tips

用类似贪心策略的分析来得到优化DP转移的结论

Code

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
#include "lucida"

const int MAXN=1e6+11;

int n;
struct Node {
	int val,h;
	bool operator <(const Node &a) const {
		return val!=a.val?val<a.val:h>a.h;
	}
}f[MAXN];
int Q[MAXN],he,ta;
int DP(int k) {
	f[1].val=0;
	Q[he=ta=1]=1;
	for(int i=2;i<=n;++i) {
		while(he<=ta && Q[he]+k<i)
			he++;
		f[i].val=f[Q[he]].val+(f[Q[he]].h<=f[i].h);
		while(he<=ta && f[i]<f[Q[ta]])
			ta--;
		Q[++ta]=i;
	}
	return f[n].val;
}
int main() {
//	freopen("input","r",stdin);
	is>>n;
	for(int i=1;i<=n;++i)
		is>>f[i].h;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		int K;is>>K;
		os<<DP(K)<<'\n';
	}
	return 0;
}