欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3042 Grazing on the Run (三维区间DP)【区间DP模板】

程序员文章站 2022-04-02 10:02:54
...

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;
}