求大佬帮调
  • 板块P1725 琪露诺
  • 楼主akahoshi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/27 15:42
  • 上次更新2024/6/27 19:28:47
查看原帖
求大佬帮调
1295409
akahoshi楼主2024/6/27 15:42
#include <bits/stdc++.h>

const unsigned maxn = 2*2e5 + 5;
const int INF = 0x3f3f3f3f;
const int nINF = 0xcfcfcfcf;

unsigned n, l, r;
int a[maxn];
int f[maxn];

std::deque<unsigned> mq;
unsigned w = 0;
inline void push(unsigned n){
	while (!mq.empty()){
		if (f[mq.back()] < f[n]){
			mq.pop_back();
		}
	}
	mq.push_back(n);
}
inline void update(){
	while (!mq.empty() || mq.front() < std::max(0, ((int)w - (int)r))){
		mq.pop_front();
	}
	push(std::max(0, ((int)w - (int)r)));
}
inline int query(){
//	std::cout << a[mq.front()];
//	std::cout << " ";
//	std::cout << mq.front() << std::endl;
	return a[mq.front()];
}

inline int dp(){
	w = l - 1;
	int v = nINF;
	// dp[i] = max(dp[n]) + a[i]
	for (unsigned i = l; i <= n; i++){
		w++;
		update();
		f[i] = std::max(f[i], query() + a[i]);
		if (i + r >= n) v = std::max(v, f[i]);
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	std::cin >> n >> l >> r;
	for (unsigned i = 0; i <= n; i++){
		std::cin >> a[i];
	}
	
	// init f[]
	memset(f, nINF, sizeof(f));
	f[0] = 0;
	for (unsigned i = 0; i < r; i++){
		f[i] = a[i];
	}
	
	std::cout << dp();
}
2024/6/27 15:42
加载中...