poj 3042 Grazing on the Run

这个题目原型应该是吃完所有的草丛的最小时间，现在变成了每个草丛被吃的时间和，貌似如果还是按照原来的dp方法dp[i][j]表示吃完i到j的草丛的花掉的时间的话，有两个因素会影响后面的决策，一个是花掉的时间，一个是吃掉的草丛的时间累加和。

但是仔细观察这个问题会发现，第一个走的距离，会被计算n次，第二个走的距离，会被计算n-1次。如果我们把这个代价转移到该草丛上的话。那么dp[i][j]表示转移后的花掉的时间，那么现在影响后面决策的就只有这个时间了。那么问题就解决了。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e3+9;
int n,l;
int a[maxn],dp[maxn][maxn][2];
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&l)!=EOF)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        n++;a[n]=l;
        sort(a+1,a+1+n);
        int t=lower_bound(a+1,a+n,l)-a;
        memset(dp,50,sizeof(dp));
        dp[t][t][0]=0;
        for(int k=0;k<n-1;k++)
        for(int i=max(1,t-k);i<=min(n,t+k);i++)
        {
            dp[i-1][i+k][0]=min(dp[i][i+k][0]+(a[i]-a[i-1])*(n-k-1),dp[i][i+k][1]+(a[i+k]-a[i-1])*(n-k-1));
            dp[i][i+k+1][1]=min(dp[i][i+k][0]+(a[i+k+1]-a[i])*(n-k-1),dp[i][i+k][1]+(a[i+k+1]-a[i+k])*(n-k-1));
        }
        int ans=min(dp[1][n][0],dp[1][n][1]);
        cout<<ans<<endl;
    }
    return 0;
}