自动搬运

查看原文

来自洛谷，原作者为

	ysj1173886760 **

搬运于2025-08-24 21:45:07，当前版本为作者最后更新于2018-09-30 07:26:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单的区间dp

可以先做关路灯，在做这道题，双倍经验。

dp[i][j][0/1]表示当前已经套完了i到j的牛，然后 第三维表示在左边还是在右边。

那么对于每次处理完区间i~j,我们如何递推出别的状态呢？

我们下一步可以选择去i-1，也就是下一步到dp[i-1][j],

或者选择去j+1,到dp[i][j+1]。

对于每一个当前的状态，fj可能在左边或者右边，也就是dp[i][j][1]或者dp[i][j][0],每一个又有两种转移方案。

两种状态一起处理就好。

我把n个点拆成了n+1个点，找到0点，设为c，令dp[c][c][0]=dp[c][c][1]=0,其他的都为inf， 两重循环转移即可，复杂度O(n^2)

主要是代码比较简洁，无压行30行，所以我想发这个题解。qaq

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1e3+10;

int n;
int pos[maxn],dp[maxn][maxn][2];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>pos[i];				//读入 
	sort(pos+1,pos+1+n);							//排个序 
	int c=lower_bound(pos+1,pos+1+n,0)-pos;			//找到0点 
	memset(dp,0x3f,sizeof(dp));						//初始化极大值 
	for(int i=n;i>=c;i--)pos[i+1]=pos[i];			//把零点以后的向右移一位，注意逆序 ，类比背包滚动数组。 
	pos[c]=0;	
	dp[c][c][0]=dp[c][c][1]=0;						//初始化起点 
	for(int l=2;l<=n+1;l++)							//开始区间dp，枚举区间长度 
		for(int i=1;i+l-1<=n+1;i++)					//枚举左端点 
		{
			int j=i+l-1;							//计算右端点 
			dp[i][j][0]=min(dp[i+1][j][0]+(pos[i+1]-pos[i])*(n-j+i+1),dp[i+1][j][1]+(pos[j]-pos[i])*(n-j+i+1));//n-j+i+1为区间大小，也就是牛的个数. 
			dp[i][j][1]=min(dp[i][j-1][1]+(pos[j]-pos[j-1])*(n-j+i+1),dp[i][j-1][0]+(pos[j]-pos[i])*(n-j+i+1));
		}
	cout<<min(dp[1][n+1][1],dp[1][n+1][0]);			//最终可能在左边或者右边. 
	return 0;
}