intellij idea使用教程 XShell 摩尔投票法 wcf join browser directory NEC Validator 支付网站建设 jquery的点击事件 jq遍历 excel太长的文字隐藏 office配置进度 matlab中不等于怎么表示 完全去vm去虚拟化工具 pyhton中异常和模块 python数据格式 python3正则表达式 python获取时间戳 python打开文件夹 java基础语言 java初学 变量的类型 java语言入门 kafka中文教程 wps2011 系统集成项目管理工程师教程 stretchcolumns 说话不算数的经典语句 骰子动态图 python电子书 俄罗斯方块代码 松下plc编程软件 五子棋大师 Mapper b450 语音转文字转换器 ps蒙版抠图 小米主题编辑器
当前位置: 首页 > 学习教程  > 编程语言

【SSL_P2883】烽火传递

2020/8/11 18:56:19 文章标签:

烽火传递


描述

烽火台又称烽燧,是重要的军事防御设施,一般建在险要或交通要道上.一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情,在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定代价.为了使情报准确地传递,在连续m个烽火台中至少要有一个发出信号.请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递.

输入

第一行:两个整数N,M.其中N表示烽火台的个数,M表示在连续m个烽火台中至少要有一个发出信号.接下来N行,每行一个数Wi,表示第I个烽火台发出信号所需代价.

输出

一行,表示答案.

样本输入

5 3 
1 
2 
5 
6 
2

样本输出

4

暗示

对于50%的数据,M≤N≤1,000。对于100%的数据,M≤N≤100 000,Wi≤10 0 0。

解题思路

做一个小DP就好

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

int n,m,a[100010],f[100010],ans=0x3f3f3f3f;
int l[100010],hd=1,tl=0;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		while(hd<=tl&&f[i-1]<=f[l[tl]]) tl--;
		l[++tl]=i-1;
		while(hd<=tl&&l[hd]<i-m) hd++;
		f[i]=f[l[hd]]+a[i];
	}
	for(int i=n-m+1;i<=n;i++)
		ans=min(f[i],ans);
	cout<<ans<<endl;
}


本文链接: http://www.dtmao.cc/news_show_100045.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?