学步园

转自：

http://www.cnblogs.com/fzf123/archive/2012/11/18/2775697.html

好久以前就看了些单调队列优化DP的资料，最近才终于搞懂是怎么回事~

这里还转了一个单调队列的例子 https://ideone.com/hyQJ3

题意：有n个垃圾，机器人要按照编号从小到大捡但手中的垃圾不得超过C，求出机器人行走的最短总路程。

做法：设dp[i]为捡第i个垃圾的最短距离，dist[i]为按顺序的总长，dis_ori[i]为i到原点的距离。

不难得出：dp[i] = min{dp[j] + dis_ori[j+1] + distance[j+1,i] + dis_ori[i] }  ;         w(j+1,i)<=C

　　　　　　　　= min{dp[j] + dis_ori[j+1] - dist[j+1]} + dist[i] + dis_ori[i] ;        w(j+1,i)<=C

用单调队列可以解决min的值，复杂度O(n) ， 注意long long。

单调队列（窗口滑动技术）：

对于每一个状态f(x)来说，计算过程分为以下几步：

　　1、 队首元素出队，直到队首元素在给定的范围中。

　　2、 此时，队首元素就是状态f(x)的最优决策。

　　3、 计算g(x)，并将其插入到单调队列的尾部，同时维持队列的单调性（不断地出队，直到队列单调为止）。

View Code 
 /*
 Author:Zhaofa Fang
 Lang:C++
 */
 #include <cstdio>
 #include <cstdlib>
 #include <sstream>
 #include <iostream>
 #include <cmath>
 #include <cstring>
 #include <algorithm>
 #include <string>
 #include <utility>
 #include <vector>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 using namespace std;
 
 typedef long long ll;
 #define DEBUG(X) cout<< #X << ':' << X << endl
 #define REP(i,n) for(int i=0;i < (n);i++)
 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
 #define PII pair<int,int>
 #define PB push_back
 #define MP make_pair
 #define ft first
 #define sd second
 #define lowbit(X) (X&(-X))
 #define INF (1<<30)
 
 
 const int maxn = 1e5+10;
 ll dp[maxn],w[maxn],dist[maxn],dis_ori[maxn];
 int X[maxn],Y[maxn];
 int q[maxn];
 ll fun(int j)
 {
     return dp[j] + dis_ori[j+1] - dist[j+1];
 }
 inline int Abs(int k)
 {
     return k>0?k:(-k);
 }
 int main()
 {
     //freopen("in","r",stdin);
     int T;
     scanf("%d",&T);
     FOR(cas,1,T)
     {
         int C,n;
         scanf("%d%d",&C,&n);
         dp[0] = dist[0] = dis_ori[0] = w[0] = X[0] = Y[0] = 0;
         FOR(i,1,n)
         {
             scanf("%d%d%lld",&X[i],&Y[i],&w[i]);
             w[i] += w[i-1];
             dist[i] = dist[i-1] + Abs(X[i]-X[i-1]) + Abs(Y[i]-Y[i-1]);
             dis_ori[i] = Abs(X[i]) + Abs(Y[i]);
         }
         int front=0,rear=0;
         q[rear++] = 0;
         FOR(i,1,n)
         {
 
             while(front < rear && w[i] - w[q[front]] > C)front++;
             dp[i] = fun(q[front]) + dist[i] + dis_ori[i];
             while(front < rear && fun(q[rear-1]) >= fun(i))rear--;
             q[rear++] = i;
         }
         printf("%lld\n",dp[n]);
     }
     return 0;
 }