求调
  • 板块P1725 琪露诺
  • 楼主Xianzi_
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/13 16:02
  • 上次更新2024/10/13 18:34:26
查看原帖
求调
591561
Xianzi_楼主2024/10/13 16:02
#include "bits/stdc++.h"
using namespace std;
int n, l, r;
int h = 1, t = 0, ans = INT_MIN;
int a[200005], dp[200005], q[200005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> l >> r;
	for (int i = 0; i <= n; i++) cin >> a[i];
	for (int i = 0; i <= n; i++){
		//do head
		while (q[h] < i - r && h <= t) h++;
		//do tail
		while (dp[q[t]] < dp[i - 1] && h <= t) t--;
		q[++t] = i - 1;
		dp[i] = dp[q[h]] + a[i];
		cout << "dp[" << i << "] = " << dp[i] << endl;
		if (i + r > n) ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}
2024/10/13 16:02
加载中...