【jzoj】 【DP】牛棚

題目

解題思路

首先兩個點之間的間距可以是r也可以是r+1(按文中（s-1）/（n-1）求出來的值

設f[i][j]為放置了i頭牛，有j個r+1的間距，最小的移動步數

假設已經放置了i-1頭牛

目前的位置是w=（j*(d+1))+((i-j-1)*d)+1，化簡為(i-1)*d+j+1

那麼轉移式為f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(w-a[i])

代碼

#include<algorithm> 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath> 
using namespace std;
int n,s,l,r,b,a[2000],f[1520][1520];
int main()
{
	freopen("graze2.in","r",stdin);
	freopen("graze2.out","w",stdout);
	memset(f,0x7f,sizeof(f));
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	r=(s-1)/(n-1);
	l=(s-1)%(n-1); 
	f[0][0]=0;
	for (int i=1;i<=n;i++)
	{
	    f[i][0]=f[i-1][0]+abs((i-1)*r+1-a[i]);  //隻有一種轉移
	    for (int j=1;j<=min(l,i-1);j++)  //i頭牛，最多有i-1個間隔
	        f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs((i-1)*r+j+1-a[i]);
    }
	printf("%d",f[n][l]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}