单调队列动态规划1——烽火传递 || 修剪草坪 || 选择数字

正常的烽火传递：LibreOJ #10180. 「一本通 5.5 练习 1」

• 题意：一列烽火台，第i个损耗为a[i]，现在选烽火台，连续m个烽火台至少有1个选上，求最小损耗

• 考虑使用暴力dp，dp[i]由dp[i-m]_{dp[i-1]中的最小值转移而来。据说会TLE}~

• 考虑使用单调队列优化dp，这题算是板子题了，一定要会做。

• 队列存的是下标

• 流程：取->转移->放

• 取之前把队首不合法的值去掉，再取队首，即为dp[i-m]~dp[i-1]中的最小值的下标

• 放之前为了保证单调性，把队尾比他大的（编号一定在他前面）都弹出，再放在队尾。

这一步的正确性：

如果一个选手比你小，还比你强，那你就可以退役了。

#include<cstdio>
#include<deque>
#define MAXN 1000005

inline int min(int x,int y){return x<y?x:y;}

int n,m,ans=1e9,a[MAXN],dp[MAXN];

std::deque<int> q;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	q.push_back(0);
	for(int i=1;i<=n;i++){
		while(!q.empty()&&q.front()<i-m)q.pop_front();
		int u=q.front();
		dp[i]=dp[u]+a[i];
		while(!q.empty()&&dp[q.back()]>dp[i])q.pop_back();
		q.push_back(i);
	}
	for(int i=n-m+1;i<=n;i++)ans=min(ans,dp[i]);
	printf("%d
",ans);
}

• <i-m调了两年，打成了<=i-m

烽火传递的补集：洛谷 P2627 修剪草坪 || P2034 选择数字

• 题意：一列奶牛，第i个利润为a[i]，现在选奶牛，选出的连续奶牛数量不超过k个，求最大利润

• 把题意转化成：连续k+1个奶牛至少有1个不选，求最小损失利润。就和烽火传递一样了。

• 题目中说了，连续奶牛不超过k个，所以连续k+1个才有必要空一个。所以读入的时候就要k++

• 注意要开longlong；ans初值要开够

#include<cstdio>
#include<deque>
#define int long long
#define MAXN 100005

inline int min(int x,int y){return x<y?x:y;}

int n,k,sum,ans=1e15,dp[MAXN],a[MAXN];

std::deque<int> q;

signed main(){
	scanf("%lld%lld",&n,&k);k++;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	q.push_back(0);
	for(int i=1;i<=n;i++){
		while(!q.empty()&&i-k>q.front())q.pop_front();
		int u=q.front();
		dp[i]=dp[u]+a[i];
		while(!q.empty()&&dp[q.back()]>dp[i])q.pop_back();
		q.push_back(i);
	}
	for(int i=n-k+1;i<=n;i++)ans=min(ans,dp[i]);
	printf("%lld
",sum-ans);
}