J解释一下程序（详细，注释）

Question

问题遇到的现象和发生背景

问题相关代码，请勿粘贴截图

#include <iostream>
using namespace std;
int f[200010],w[200010], q[200010];
int main() {
    int n, m,hh = 0, tt = 0;
    cin>>n>>m;
    for (int i = 1; i <= n; i ++)cin>>w[i];
    f[0] = 0;
    q[tt] = 0;
    for (int i = 1; i <= n; i ++) {
        if (hh <= tt && q[hh] + m < i) hh ++;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++ tt] = i;
    }
    int res = 100000000;
    for (int i = n - m + 1; i <= n; i ++) res = min(res, f[i]);
    cout << res << endl;
    return 0;
}

运行结果及报错内容

题目描述
烽火台是重要的军事防御设施，一般建在交通要道或险要处。

一旦有军情发生，则白天用浓烟，晚上有火光传递军情。

在某两个城市之间有n nn 座烽火台，每个烽火台发出信号都有一定的代价。

为了使情报准确传递，在连续 m mm 个烽火台中至少要有一个发出信号。

现在输入 n , m n,mn,m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入格式
 
第一行是两个整数 n ,    m  n,  m  n,  m，具体含义见题目描述；

第二行 n nn 个整数表示每个烽火台的代价 a i a_ia 
i
​
 。

输出格式

输出仅一个整数，表示最小代价。

数据范围

1 ≤ n , m ≤ 2 × 1 0 5 1≤m,n≤2×10^51≤ n, m≤2×10 
5
 ,
0 ≤ a i ≤ 1000 0≤a_i≤10000≤a 
i
​
 ≤1000

输入样例

5 3
1 2 5 6 2

输出样例

4

Answer 1

自己提供一种更加简洁的写法，直接利用nums数组来存储我们整个DP过程中的最小值，每次遍历到i时，nums[i]中存放的就是满足题目限制条件，并且点亮第i个烽火台的最小代价，然后我们把这个最优值加入队列。由于我们需要求出最后m大小的窗口里，最小的那个值，所以直接取此时单调队列对头的元素即可。

#include <iostream>
using namespace std;

const int N = 2e5 + 10;
int n, m;
int nums[N];
int q[N], head, tail;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
        cin >> nums[i];

    head = 0, tail = 0;
    for (int i = 1; i <= n; ++i)
    {
        nums[i] += nums[q[head]];
        if (q[head] <= i - m) ++head;
        while (head <= tail && nums[i] <= nums[q[tail]]) --tail;
        q[++tail] = i;
    }

    cout << nums[q[head]] << endl;
    return 0;
}