0分求调
  • 板块P1725 琪露诺
  • 楼主Andy_hpy
  • 当前回复5
  • 已保存回复5
  • 发布时间2025/8/31 12:08
  • 上次更新2025/8/31 21:06:51
查看原帖
0分求调
1039717
Andy_hpy楼主2025/8/31 12:08
/*
dp[i] = max{dp[i - l], dp[i - l + 1], ..., dp[i - r]} + a[i];
dp[i] = -INF;
dp[0] = 0;
ANS = max{dp[n - r + 1], dp[n - r + 2], ..., dp[n]};
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef __int128 LL;
const ll MAXN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = INT_MAX;
const ll LINF = LLONG_MAX;
const db EPS = 1e-5;
ll n, l, r, a[MAXN], dp[MAXN];
struct node
{
    ll val, pos;
};
deque<node> q;
int main(){
    cin >> n >> l >> r;
    for (int i = 1; i <= n + 1; i++){
        cin >> a[i - 1];
    }
    memset(dp, ~0x3f, sizeof dp);
    dp[0] = 0;
    q.push_back({0, 0});
    for (int i = l; i <= n; i++){
        while (!q.empty() && q.front().pos < i - r){
            q.pop_front();
        }
        dp[i] = q.front().val + a[i];
        while (!q.empty() && q.back().val <= dp[i - l]){
            q.pop_back();
        }
        q.push_back({dp[i - l], i - l});
    }
    ll ans = -LINF;
    for (int i = n - r + 1; i <= n; i++){
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}
2025/8/31 12:08
加载中...