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

poj 3042 Grazing on the Run

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

这个题目原型应该是吃完所有的草丛的最小时间,现在变成了每个草丛被吃的时间和,貌似如果还是按照原来的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;
}