P1313 [NOIP2010初赛]烽火传递
时间: 1000ms / 空间: 131072KiB / Java类名: Main
描述
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。
输入格式
第一行有两个数n,m分别表示n个烽火台，在m个烽火台中至少要有一个发出信号。
第二行为n个数，表示每一个烽火台的代价。
第二行为n个数，表示每一个烽火台的代价。
输出格式
一个数，即最小代价。
测试样例1
输入
5 3
1 2 5 6 2
输出
4
备注
1<=n,m<=1,000,000
先上50分代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e3+;
const int inf=2e9;
int n,m,a[N*];
int dp[N][N];
int dfs(int x,int y){//dp[x][y]表示选到第x个，已经空了y个（没有发出信号）
if(y==m) return inf;
if(x==n+) return ;
if(dp[x+][y+]!=-) dp[x][y]=dp[x+][y+];
else dp[x][y]=dfs(x+,y+);
if(dp[x+][]!=-) dp[x][y]=min(dp[x][y],dp[x+][]+a[x+]);
else dp[x][y]=min(dp[x][y],dfs(x+,)+a[x+]);
return dp[x][y];
}
int main(){
memset(dp,-,sizeof dp);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
dfs(,);
printf("%d",dp[][]);
return ;
}
前言：
自己对于单调队列的一点理解：
for(;l<r&&i-q[l]>m;l++);//队列里一定要有一个元素且不合法才出队(删除前面)
f[i]=f[q[l]]+a[i];//用队首来更新当前f[i]的答案
for(;l<r&&f[q[r]]>f[i];r--);//用当前的f[i]去更新队尾，使队列保持单调性(删除后面)
q[++r]=i;//进队
解析：
设f[i]表示点燃当前位置烽火台，且前i个满足要求的最小代价。
显然就有f[i]=min(f[j])+a[i]（i-m<=j<=i-1）。
当然，这会超时，所以要有优化。
优化一：肯定是从前m个里选小的，涉及到区间最小值，可用线段树，时间复杂度将为O（n log m）。
优化二：同样因为要选前m个最小的，使用单调队列，队列里存有不超过m个长度单位的值，每次取队首，进队时维护队列使其单调不下降，复杂度将为O（n）。
(这里主要讲解 优化二即单调队列)
AC代码：
#include<cstdio>
#include<algorithm>
using namespace std;
inline const int read(){
register int x=,f=;
register char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
const int N=1e6+;
int n,m,l,r,a[N],f[N],q[N<<];
int main(){
n=read();m=read();
for(int i=;i<=n;i++) a[i]=read();
l=r=;
for(int i=;i<=n;i++){
for(;l<r&&i-q[l]>m;l++);
f[i]=f[q[l]]+a[i];
for(;l<r&&f[q[r]]>f[i];r--);
q[++r]=i;
}
int ans=0x7fffffff;
for(int i=n-m+;i<=n;i++) ans=min(ans,f[i]);
printf("%d",ans);
return ;
}