幽默单调队列样例输出24求助
查看原帖
幽默单调队列样例输出24求助
510555
ImposterAnYu楼主2024/8/8 14:32
#include <bits/stdc++.h>
#define int1 long long
#define N 100000
#define ANS(x) (dp[x][0] - sum[x])//单调队列维护的东西 
using namespace std;
int1 n,k,i,dp[N + 5][0],sum[N + 5],q[N + 5],head,tail;
int1 read(){//快读 
	int1 x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)){
		if (ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void uprint(int1 x){//快写 
	if (x >= 10){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){//快写 
	if (x < 0){
		putchar('-');
		x = -x;
	}
	uprint(x);
	return ;
}
void ps(int1 x){//快写+空格 
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){//快写+换行 
	print(x);
	putchar('\n');
	return ;
}
int main(){
//原理:dp[i][1]=max(dp[j][0]-sum[j])+sum[i](i-k<=j<i)
//dp[i][0]=max(dp[i-1][0],dp[i-1][1])
//用单调队列维护dp[j][0]-sum[j]以O(1)更新dp[i][1] 
	n = read(),k = read();
	for(i = 1; i <= n; i++){
		sum[i] = sum[i - 1] + read();//前缀和 
	}
	head = 1,tail = 0;
	for(i = 1; i <= n; i++){
		dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
		while(q[head] < i - k && head <= tail){//弹出队头 
			head++;
		}
		dp[i][1] = ANS(q[head]) + sum[i];//更新答案 
		while(ANS(i) > ANS(q[tail]) && head <= tail){//弹出队尾 
			tail--;
		}
		q[++tail] = i;//加入新元素 
	}
	pe(max(dp[n][0],dp[n][1]));
	return 0;
}
2024/8/8 14:32
加载中...