A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1742 [Usaco2005 nov]Grazing on the Run 边跑边吃草 区间dp
发表于: | 分类: Oi | 评论:0 | 阅读:48

第一次$inf$搞小了,直接玩脱了
但是这还是一道挺简单的题
首先先要明确牛的路线,妞一定是先走到左面,再走到右面,再走到左面……
而且如果牛路过了草却没有顺便吃掉,牛的思想就有问题
然后就比较简单了
我们用$f(i,j,0)$表示从$i$到$j$全部吃完,最后在左端点,$f(i,j,1)$表示从$i$到$j$全部吃完,最后在右端点
然后分成四种情况讨论就行了

写完之后本来还想看看有没有别的解法,结果上网上一看连代码都一样,一脸懵逼……【雾

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000+5;
const LL inf = 1000000000000ll;
#define max(a,b) ((a)>(b)?(a):(b))

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

LL f[N][N][2],a[N];

int main()
{
    int n , x;
    cin  >> n >> x;
    for(int i=1;i<=n;++i)
        a[i] = read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
        f[i][i][0] = f[i][i][1] = abs(a[i]-x)*n;
    for(int len=2;len<=n;++ len)
        for(int i=1;i+len-1<= n;++ i)
        {
            int j=i+len-1;
            f[i][j][0] = f[i][j][1] = inf;
            f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(LL)(n-(j-i))*(a[i+1]-a[i]));
            f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(LL)(n-(j-i))*(a[j]-a[i]));
            f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(LL)(n-(j-i))*(a[j]-a[i]));
            f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(LL)(n-(j-i))*(a[j]-a[j-1]));
        }
    cout<<min(f[1][n][0],f[1][n][1]);
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP