真就纯纯爆零？
\(T1\) \(P4823\) \([TJOI2013]拯救小矮人\)

一群矮人掉进了深度为 \(H\) 的坑，每个矮人身高 \(A[i]\)，手臂长为 \(B[i]\)，如果我们利用矮人 \(1\)，矮人 \(2\)，矮人 \(3\)，……，矮人 \(k\) 搭一个梯子，满足 \(A_1+A_2+A_3+\dots+A_k+B_k \geq H\) 那么矮人 \(k\) 就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就不能再搭人梯了。试问最多有多少矮人可以逃跑。

怎么nm \(DP\) 都不会了。

考场上靠按照 \(a\) 从小到大排序可以水过去。当然，数据很水。
那么按照 \(a+ b\) 的顺序从小到大排序，顺序越靠前，说明他自己跑出坑的能力越大。因此可以排序后贪心地进行 \(DP\)，这也是dp中常用的方法罢。贪心与dp要相结合。

考场上这道题大概是第三开的吧，十几分钟想了想，写了个按 \(a\) 排序的伪贪心就走了，甚至都没编译一下。但是这个方法在这个水数据下可以拿满，结果 \(scanf\) 写错了，痛失100pts，令人感慨。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3;
int n,H,tot,ans,dp[MAXN + 5];
struct HUMAN{
	int a,b;
}hum[MAXN + 5];
bool cmp(HUMAN a,HUMAN b){
	return a.a + a.b < b.b + b.a;
}
int main(){
	freopen("escape.in","r",stdin);
	freopen("escape.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)scanf("%d%d",&hum[i].a,&hum[i].b),tot += hum[i].a,dp[i] = -0x3f3f3f3f;
	scanf("%d",&H);
	sort(hum + 1,hum + 1 + n,cmp);
	dp[0] = tot;
	for(int i = 1; i <= n; i++){
		for(int j = i; j >= 1; j--){
			if(dp[j - 1] + hum[i].b >= H)dp[j] = max(dp[j],dp[j - 1] - hum[i].a);
		}
	}
	for(int i = n; i >= 1; i--){
		if(dp[i] >= 0){
			 cout << i;
			return 0;
		}
	}
	cout << 0;
}

\(T2\) \(CF1237D\) \(Balanced\) \(Playlist\)
还是做过的原题……

一个小细节就是要有化环为链的思想。

发现区间中是否存在 \(a_i > a_j * 2,j > i\) 这种情况可以用线段树来进行维护，套个二分就行了，不过只能过 \(n <= 1e5\) 的原题。

另一种方法就是单调队列，很久没写这个了，在这里说一下。

单调队列/单调栈是通过维护队列/栈内数据的有序性来实现处理区间问题的数据结构。在这个题里，维护一个从队首到队尾单调递减的单调队列。每便利一个新元素时就把它丢进去，看看是否存在队首元素大于它的两倍。

考场上是第一个开的题，打了方法一就走了。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 5e5;
int n,m[MAXN + 5],mn,mx,q[MAXN + 5],ans[MAXN + 5],b[MAXN + 5];
int main(){
	freopen("song.in","r",stdin);
	freopen("song.out","w",stdout);
	scanf("%d",&n);
	mn = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++){
		scanf("%d",&m[i]);
		m[i + n] = m[i + 2 * n] = m[i];
		mn = min(m[i],mn);
		mx = max(m[i],mx);
	}
	if(mn * 2 >= mx){
		for(int i = 1; i <= n; i++)printf("-1 ");
		return 0;
	}
	int l = 0,r = 0;
	for(int i = 1; i <= 3 * n; i++){
		while(l <= r && q[r] < m[i]){
			r--;
		}
		q[++r] = m[i];
		b[r] = i;
		while(l <= r && m[i] * 2 < q[l]){
			ans[b[l]] = i - b[l];
			l++;
		}
	}
	for(int i = 3 * n; i >= 1; i--){
		if(!ans[i])ans[i] = ans[i + 1] + 1;
		if(ans[i] >= 2 * n)ans[i] = -1;
	}
	for(int i = 1; i <= n; i++)cout << ans[i] << " ";
}