《算法竞赛进阶指南》0x55环形与后效处理DP 环路运输
题目链接：https://www.acwing.com/problem/content/291/
题目给出的是一个环状公路，公路上有n个点，每个点都有一个值w[i]，点之间的距离就是从两点沿着环的最短路径，问最大的w[i]+w[j]+dis(i,j)是多少。
由于这个dis不会超过n/2，所以可以枚举一个点i，对[i-n/2,i-1]区间查找w[i]-i的最大值。将环变成链状处理即可，这里由于一段区间计算的值只和端点有关，是一个滑动窗口求最值的问题，通过单调队列可以在O(N)时间内求解。维护一个长度不超过len=n/2而且单调下降的序列的索引。
单调队列中，假设k<j<i且维护的属性值T[k]<T[j]，那么在不失更好的决策的情况下是不会保留k的，因为明显j更大而且j更加靠近i。
代码：
#include<iostream> #include<cstdio> using namespace std; const int maxn = 2000010; int w[maxn]; int q[maxn]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&w[i]); w[i+n]=w[i]; } int l=1,r=1; int len=n/2; int ans=-1; for(int i=1;i<=n*2;i++){ if(l<=r && q[l]<i-len)l++; ans=max(ans,w[i]+w[q[l]]+i-q[l]); while(l<=r && w[q[r]]-q[r]<=w[i]-i)r--; q[++r]=i; } cout<<ans<<endl; return 0; }