POJ 3042 Grazing on the Run （三维区间DP）【区间DP模板】

A long, linear field has N (1 <= N <= 1,000) clumps of grass at unique integer locations on what will be treated as a number line.Think of the clumps as points on the number line. 

Bessie starts at some specified integer location L on the number line (1 <= L <= 1,000,000) and traverses the number line in the two possible directions (sometimes reversing her direction) in order to reach and eat all the clumps. She moves at a constant speed (one unit of distance in one unit of time), and eats a clump instantly when she encounters it. 

Clumps that aren't eaten for a while get stale. We say the "staleness" of a clump is the amount of time that elapses from when Bessie starts moving until she eats a clump. Bessie wants to minimize the total staleness of all the clumps she eats. 

Find the minimum total staleness that Bessie can achieve while eating all the clumps.

Input

* Line 1 : Two space-separated integers: N and L. 
* Lines 2..N+1: Each line contains a single integer giving the position P of a clump (1 <= P <= 1,000,000). 

Output

* Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.

Sample Input

4 10
1
9
11
19

Sample Output

44

Hint

INPUT DETAILS: 
Four clumps: at 1, 9, 11, and 19. Bessie starts at location 10. 

OUTPUT DETAILS: 
Bessie can follow this route: 
* start at position 10 at time 0 
* move to position 9, arriving at time 1 
* move to position 11, arriving at time 3 
* move to position 19, arriving at time 11 
* move to position 1, arriving at time 29

 【题解】这是一道区间DP题，刚开始我用模拟做，WA了几发后，发现有的数据不满足，不得不想别的方法，研究发现这个可以用区间DP来做，就是递推式比较麻烦，难想，还是参考了大神的递推式才写出来的。

lower_bound和upper_bound算法详解：http://http://blog.csdn.net/qq_38538733/article/details/75212045

 

 题意：在一维上有n块草坪，给出每块草坪的位置（可以看做是x轴上的整数点），Bessie初始位于L位置，他可以向左右两个方向去吃草坪，假设吃草坪的时间不计，路上的时间是每走一个单位，时间+1，每块草坪都有一个staleness值，这个值恰好等于Bessie到达的时间，现在要求的是Bessie将所有草坪吃完，所有草坪的staleness值之和最小。

思路：这是一道区间DP的问题，我们用dp[i][j][0]表示从i-j区间都吃完，最后停留在i位置，所有草坪的最小的staleness值；dp[i][j][1]表示i-j区间都吃完，最后停留在j位置，所有草坪的最小的staleness值。（显然i~j都吃完之后不可能停在中间。因为如果i、j都吃完了，那么从i到j或者从j到i必然经过了中间的所有点）。那么这两个状态的转移方程就是：

dp[i][j][0] = min(dp[i+1][j][0]+(s[i+1]-s[i])*k , dp[i+1][j][1]+(s[j]-s[i])*k);//k是剩下多少草没吃，它们的staleness值要增加，而s[i+1]-s[i]之类的是最后一段行走的距离，也即增加量。
dp[i][j][1] = min(dp[i][j-1][0]+(s[j]-s[i])*k , dp[i][j-1][1]+(s[j]-s[j-1])*k);

       其中k = n-(j-i);

       我把起始点也添加进了草点，这样便于计算。

  剩下的就自己悟吧，这个重点就是递推关系式。

 【AC代码】

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1005;
const int INF=0x3fffffff ;//一定要初始化的足够大   不然会WA
int m,n;
int a[N];
int dp[N][N][2];

int min(int x,int y)
{
    return x>y?y:x;
}

int main()
{
    int k;
    while(~scanf("%d %d",&m,&n))
    {
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]);
        a[++m]=n;//吧初始点也加进去
        sort(a+1,a+m+1);
        n=lower_bound(a+1,a+m+1,n)-a;//返回第一个大于等于n的数的位置  不懂自行百度

        for(int i=0;i<=m;i++)
            for(int j=0;j<=m;j++)
               dp[i][j][0]=dp[i][j][1]=INF;
        dp[n][n][0]=dp[n][n][1]=0;

        for(int i=n;i>=1;--i)
        {
            for(int j=n;j<=m;j++)
            {
                if(i==j) continue;//
                k=m-(j-i);
                dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*k,dp[i+1][j][1]+(a[j]-a[i])*k);
                dp[i][j][1]=min(dp[i][j-1][0]+(a[j]-a[i])*k,dp[i][j-1][1]+(a[j]-a[j-1])*k);
            }
        }
        printf("%d\n",min(dp[1][m][0],dp[1][m][1]));
    }
    return 0;
}