烽火传递

标签：个点 int tt 传递 ++ hh include 烽火

单调队列优化DP

原题链接

题目描述

给定一个长度为n的数组a,a[i]代表第i个点的价值，要求选择某些点，使得满足选择的点满足：

• 两点之间下标之差不超过m
• 总价值最小

分析

状态定义：
设\(f_i\)表示从\(1\sim i\)中选择方案，且选择第i个点的方案的最小代价
状态转移：

\[f_i=a_i + min\{f_j\}\quad(i-m+1\leq j\leq i-1) \]

即从区间[i - m + 1, i - 1]中找最小值，很自然想到滑动窗口
答案为区间[n - m + 1, n]中的最小值，可以将窗口往后滑动一格，即为答案

#include <iostream>
#include <cstring>

constexpr int N = 2e5 + 5;

int a[N], q[N];
int f[N];

int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) std::cin >> a[i];
    
    int hh = 0, tt = -1;
    f[0] = 0, q[ ++ tt] = f[0];
    for (int i = 1; i <= n; i ++ ) {
        if (hh <= tt && i - q[hh] > m) hh ++ ;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }
    
    // 对头滑出窗口，往后滑一格
    if (n + 1 - q[hh] > m) hh ++ ;
    int res = f[q[hh]];
    
    std::cout << res << '\n';
    return 0;
}

标签：个点,int,tt,传递,++,hh,include,烽火
From： https://www.cnblogs.com/zjh-zjh/p/16716348.html