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

bzoj 1742: [Usaco2005 nov]Grazing on the Run 边跑边吃草【区间dp】

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

挺好的区间dp,状态设计很好玩
一开始按套路设f[i][j],g[i][j]为吃完(i,j)区间站在i/j的最小腐败值,后来发现这样并不能保证最优
实际上是设f[i][j],g[i][j]为从i开始吃j个,站在这段区间的左/右端点的 * 最小所有草增加的腐败值 * ,因为这些腐败之最后也是要算进去的,所以直接夹在里面就可以保证最优

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
long long n,m,l,r,f[N][2],g[N][2],a[N];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=m)
            l=i;
        if(!r&&a[i]>m)
            r=i;
    }
    memset(f,0x3f,sizeof(f));
    memset(g,0x3f,sizeof(g));
    if(l)
        f[l][1]=g[l][1]=n*(m-a[l]);
    if(r) 
        f[r][1]=g[r][1]=n*(a[r]-m);
    for(int k=2;k<=n;k++)
        for(int i=1;i+k-1<=n;i++)
        {
            int j=i+k-1;
            f[i][k&1]=min(f[i+1][~k&1]+(n-k+1)*(a[i+1]-a[i]),g[i+1][~k&1]+(n-k+1)*(a[j]-a[i]));
            g[i][k&1]=min(g[i][~k&1]+(n-k+1)*(a[j]-a[j-1]),f[i][~k&1]+(n-k+1)*(a[j]-a[i]));
        }
    printf("%lld\n",min(f[1][n&1],g[1][n&1]));
    return 0;
}