自动搬运

查看原文

来自洛谷，原作者为

	一叶知秋。 エミリアたん·マジ·天使

搬运于2025-08-24 22:19:31，当前版本为作者最后更新于2020-06-01 16:09:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

DP裸题，考虑怎么设状态

设 $f[i][j][x][y] (i \le n,j\le(i+1)/2,x<2,y<2)$

表示前 $i$ 座山中有 $j$ 座用来造房子，第 $i-1$ 座山与第 $i$ 座山的状态分别为 $x$ 和 $y$ （ $0$ 表示不建房子， $1$ 反之）的最小花费，然后转移，最后输出时在几种状态中取小即可

具体实现看代码：

#include<cstdio>
#include<cctype>

#define maxn 5555

inline int read(){
	int r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

inline int min(int a,int b){
	return a<b?a:b;
}

inline int val(int x){
	return x<0?0:x;
}

int n,a[maxn],f[maxn][maxn][2][2];

int main(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		f[i][0][1][0]=1e9+10;
		for(int j=1;j<=((n+1)>>1);j++)
			for(int x=0;x<2;x++)
				for(int y=0;y<2;y++)
					f[i][j][x][y]=1e9+10;
	}
	f[1][0][0][0]=f[1][1][0][1]=0;
	a[0]=1e9;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=((i+1)>>1);j++){
			f[i][j][0][0]=min(f[i-1][j][1][0],f[i-1][j][0][0]);
            //这条转移显然
			f[i][j][1][0]=f[i-1][j][0][1]+val(a[i]-a[i-1]+1);
            //因为不能挨着建，所以[1][0]只能由[0][1]转移而来
			f[i][j][0][1]=min(f[i-1][j-1][0][0]+val(a[i-1]-a[i]+1),f[i-1][j-1][1][0]+val(min(a[i-2]-1,a[i-1])-a[i]+1));
            //注意，如果是由[1][0]转移过来的话，那么第i-1座山已经小于a[i-2]了，不需要算两遍
		}
	for(int i=1;i<=((n+1)>>1);i++){
		int ans=1e9+10;
		for(int x=0;x<2;x++)
			for(int y=0;y<2;y++)
				ans=min(ans,f[n][i][x][y]);
		printf("%d ",ans);
	}
	return 0;
}