python/TangDou/AcWing/MonotonicQueue/1089_BruteForce.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 200010;
int f[N];
int w[N], n, m;

//  通过了 11/12个数据
int main() {
    /**
    普通DP大法
    状态表示：
     ①集合:f[i]表示前i个灯塔满足条件，并且i点亮。
     ②属性：最小代价
    状态计算：f[i]=min(f[j]+w[i]) (i−m≤j≤i−1)
    答案：(n−m+1)~n必须有灯塔亮，所以枚举一下求出最小值即可
    */
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];

    //初始化
    memset(f, 0x3f, sizeof f);              //预求最小，先设最大
    f[0] = 0;                               //需要手动初始化一下递推的base case
    //依题意，f[1]代表第1个灯塔点亮需要付出的代价是w[1],也就是f[0]=0,想想也正常，虚拟第0个点亮成本为0~
    for (int i = 1; i <= n; i++)
        for (int j = max(0, i - m); j <= i - 1; j++)    //向前查看它之前的m个
            f[i] = min(f[i], f[j] + w[i]);

    int res = INF;
    for (int i = n + 1 - m; i <= n; i++) res = min(res, f[i]);
    printf("%d\n", res);
    return 0;
}