Sequences hoj 单调队列优化DP
/*可以用单调队列优化的DP一般是用于限定长度的区间，且区间有整体移动的趋势。即每一个元素是逐次进出区间，且只有一次。这样的题目一般都是有比较明显的模板。下面的这个就是集训的时候学长给的模板。感觉挺好写和理解。不过综合对比时间效率。感觉不一定是最高效的。题意是给你固定的区间长度范围。求该序列首端和末端的和最大值。简单。维护一个单调队列进行优化即可。有些细节看代码的注释。*/#include <iostream>#include <stdio.h>#include <cstring>#define maxn 100010//#define inf -1000000000#define inf 0x7fffffffusing namespace std;struct node{ int num,id; node() {} node(int _num,int _id) { num=_num; id=_id; }} q[maxn];int dp[maxn];int a[maxn];int main(){ int n,m,len; while(scanf("%d",&len)==1) { dp[0]=0; scanf("%d%d",&n,&m); for(int i=1; i<=len; i++) if(i<=n-1) dp[i]=inf;//1到n-1没有意义 int head=0,rear=0; q[rear++]=node(0,1); for(int i=1; i<=len; i++) { scanf("%d",&a[i]); if(i>=n) { while(head<rear&&q[rear-1].num<=dp[i-n]+a[i-n+1]) rear--;//将i-n加入,i-m已经在队列中. q[rear++]=node(dp[i-n]+a[i-n+1],i-n); while(head<rear&&i-q[head].id>m) head++;//注意是>m..知道找到<=m时跳出.<=m是我们需要的情况 dp[i]=q[head].num+a[i]; } } printf("%d\n",dp[len]); } return 0;}