1602：烽火传递

// 1602：烽火传递.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>
using namespace std;

/*
* https://loj.ac/p/10180
http://ybt.ssoier.cn:8088/problem_show.php?pid=1602
原题来自：NOIP 2010 提高组初赛 · 完善程序

烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。

在某两个城市之间有 n
 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 m
 个烽火台中至少要有一个发出信号。现在输入 n,m
 和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。

【输入】
第一行是 n,m，表示 n 个烽火台和连续烽火台数 m；

第二行 n 个整数表示每个烽火台的代价 ai。

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

【输入样例】
5 3
1 2 5 6 2
【输出样例】
4

对于全部数据，1<= n,m<= 2 * 10^5,1<= a_i<= 1000。
*/

const int N = 200010;
int dp[N];
int arr[N];
int n, m;


int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = max(0, i - m); j < i; j++) {
			dp[i] = min(dp[i], dp[j] + arr[i]);
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = n; i >= max(n - m + 1, 1); i--) {
		ans = min(ans, dp[i]);
	}

	cout << ans << endl;

	return 0;
}

视频题解空间