摘要
Title: 1089. 烽火传递
Tag: 单调队列、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

1089. 烽火传递

题意

烽火台是重要的军事防御设施，一般建在交通要道或险要处。
一旦有军情发生，则白天用浓烟，晚上有火光传递军情。
在某两个城市之间有 n座烽火台，每个烽火台发出信号都有一定的代价。
为了使情报准确传递，在连续 m个烽火台中至少要有一个发出信号。
现在输入 n,m和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
思路

单调队列优化dp

状态表示： f[i]表示前1—i座烽火台满足条件，且第i座烽火台点燃的方案集合。
属性：所有符合条件的方案集合中的最小代价值。

最后 $res = min{f_i} (n-m+1 \le i \le n)$ 也就是在最后一段找最小值，就是最后一段里必须挑一个点燃，看看是哪个f[i]最小，就点哪个

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-23 23:39:55
* @FilePath: \Acwing\1089\1089.cpp
* @LastEditTime: 2023-02-23 23:48:23
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int f[N], a[N];
signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    deque<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; ++i)
    {
        while (SZ(q) && i - q.front() > m)
            q.pop_front();
        f[i] = f[q.front()] + a[i];
        while (SZ(q) && f[q.back()] >= f[i])
            q.pop_back();
        q.push_back(i);
    }

    int res = INF;
    for (int i = n - m + 1; i <= n; ++i)
        res = min(res, f[i]);

    cout << res;
    return 0;
}

1089. 烽火传递

题意

思路

代码