标签：std 修剪 int max ll leq hh 草坪

原题链接

题目描述

给定一个长度为n的数组a和一个整数m，a[i]表示i点的价值，从a中选择一些元素：

• 不能选择连续m个元素
• 使得总价值最大

分析

令f[i]表示以i为右端点的前缀区间的最大价值
状态转移：
考虑第i个物品选或不选

• 不选：

\[f_i=f_{i-1} \]

• 选：

\[f_i=f_{i-j-1}+s_i-s_{i-j}\quad(j是以i为右端点的连续选择的区间长度，0\leq j\leq m) \]

整理得：\(f_i=s_i+max\\{f_{j-1}-s_j\\}\quad 0\leq i-j\leq m\)

#include <iostream>
#include <cstring>

using ll = long long;

constexpr int N = 1e5 + 5;

int n, m;
ll s[N], f[N];
int q[N];

// 返回
ll g(int i) {
    return f[std::max(0, i - 1)] - s[i];
}

int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) std::cin >> s[i], s[i] += s[i - 1];
    
    int hh = 0, tt = -1;
    q[ ++ tt] = f[0];
    for (int i = 1; i <= n; i ++ ) {
        if (hh <= tt && i - q[hh] > m) hh ++ ;
        f[i] = std::max(f[i - 1], g(q[hh]) + s[i]);
        while (hh <= tt && g(q[tt]) <= g(i)) tt -- ;
        q[ ++ tt] = i;
    }
    
    std::cout << f[n] << '\n';
    return 0;
}

标签：std,修剪,int,max,ll,leq,hh,草坪
From： https://www.cnblogs.com/zjh-zjh/p/16717133.html