JDOJ-1056: 烽火传递

[文章目录]

Description

在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定代价。为了使情报准确地传递,在连续m个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传递。

单调队列优化DP,原来想法是以能覆盖到第几个为状态,循环点;但是时间是n*m的,因为每个点都要维护和其相连的f[];后来改变状态,f[i]表示选第i个点时的最小体力,这样的话,状态之间的关系就是对于每一个点x,他前面[i-m,i-1]的点至少有一个得选,所以,用单调队列维护这个区间的最小值,每次直接用,作为新的f[];然后再更新单调队列,进行DP。

注意的是:que[]里存的是第几个点,并不是最小体力,以便于判断区间是否已经掠过该点

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int val[101000];
long long f[101000];
int que[101000];
int head=1,tail=1;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int i=1;i<=n;i++)
	{
		f[i]=f[que[head]]+val[i];
		while(tail>=head&&f[i]<=f[que[tail]])
			tail--;
		que[++tail]=i;
		while(que[head]<i+1-m)
			head++;
	}
	printf("%lld",f[que[head]]);
	return 0;
}

好难QAQ,做了1.5h,感觉自己好弱智!!!

发表评论

邮箱地址不会被公开。 必填项已用*标注