5 3 1 2 5 6 2
4
看了原题，发现数据范围根本不是动态规划hold住的，最终优化为单调队列
最初始的动规：设f[i]表示点燃当前位置烽火台，且前i个满足要求的最小代价。
显然就有f[i]=min(f[j])+a[i]（i-m<=j<=i-1）。
当然，这会超时，所以要有优化。
优化一：肯定是从前m个里选小的，涉及到区间最小值，可用线段树，时间复杂度将为O（n log m）。
优化二：同样因为要选前m个最小的，使用单调队列，队列里存有不超过m个长度单位的值，每次取队首，进队时维护队列使其单调不下降，复杂度将为O（n）。
单调队列
需要注意
1.队列中存储的不是元素本身，而是输入的序号
2.队列要保持单调递增，只有这样，才能保证队列中每个元素都有成为最小元素的可能
#include<iostream> using namespace std; #define MAXN 1000010 int n,m,l,r,a[MAXN],f[MAXN],q[MAXN<<1]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; l=r=0; for(int i=1;i<=n;i++){ while(l<r&&i-q[l]>m)l++;//队列不为空且队首元素不合法 f[i]=f[q[l]]+a[i];//用队首更新答案 while(l<r&&f[q[r]]>f[i])r--;//更新队尾，使队列保持单调性 q[++r]=i;//进队 } int ans=0x7fffffff; for(int i=n-m+1;i<=n;i++)ans=min(ans,f[i]); cout<<ans; return 0; }
原文：http://www.cnblogs.com/thmyl/p/6361177.html