bzoj千题计划152：bzoj3405: [Usaco2009 Open]Grazing2 移动牛棚

http://www.lydsy.com/JudgeOnline/problem.php?id=3405

n个牛棚，n-1段

因为要求距离尽量大，而且尽可能多的为d

所以：

第1个牛棚一定在位置1

最后一个牛棚一定在位置s

每段距离不是d就是d+1

有s-（n-1）*d-1段 d+1，其余段距离为d

dp[i][j] 表示前i个牛棚，有j段距离为d+1

那么第i个牛棚的位置就是d*（i-1）+j+1

第i个牛棚要么与上一个距离为d，要么距离为d-1

所以转移方程为 dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+abs(pos[i]-(i-1)*d-j-1);

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;#define N 1501int dp[N][N];int pos[N];void read(int &x)
{
    x=; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}int main()
{
    int n,s;
    read(n); read(s);
    for(int i=;i<=n;++i) read(pos[i]);
    int d=(s-)/(n-);
    int m=s-(n-)*d-;
    sort(pos+,pos+n+);
    memset(dp,,sizeof(dp));
    dp[][]=pos[]-;
    for(int i=;i<=n;++i)
    {
        dp[i][]=dp[i-][]+abs(pos[i]-d*(i-)-);
        for(int j=;j<=m && j<i;++j)
            dp[i][j]=min(dp[i-][j],dp[i-][j-])+abs(pos[i]-(i-)*d-j-);
    }
    cout<<dp[n][m];
}