自动搬运

查看原文

来自洛谷，原作者为

	T_Q_X AFO

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

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

以下是正文

---

传送门

洛谷P5336

可能更好的体验

---

容易发现这是道区间DP题目，于是走流程：

一.定义状态

• 根据答案，考虑 $f[l][r]$ 表示区间 $[l,r]$ 中的成绩单全部被发放需要的最小代价，那么答案就是 $f[1][n]$ 。

• 但是这道题目的发放成绩单方式比较奇妙，发放一段区间可能可以先在区间中随意选择一些部分来发放，再将剩下的部分发放。

• 注意到分发代价只与一段区间中分数的 $max$ 与 $min$ 有关，于是我们令 $g[l][r][mn][mx]$ 为区间 $[l,r]$ 中的所有成绩单发放一部分后剩下的成绩单的分数最大值为 $mx$ ，最小值为 $mn$ 时的最小代价

• 于是有

$$f[l][r]=min(g[l][r][mn][mx]+a+b*(mx-mn)^2)$$

---

二.状态转移

• 考虑$g[l][r][mn][mx]$加入新成绩单 $r+1$ 时的转移：

• 1.保留第$r+1$张成绩单不取走，未来与 $[l,r]$ 中的成绩单共同取走：

$$g[l][r+1][min(mn,w[r+1])][max(mx.w[r+1])] =min(g[l][r][mn][mx]) $$

• 2.枚举 $k$，将 $[r+1,k]$ 这段区间的成绩单共同取走

$$g[l][k][mn][mx]=min(g[l][r][mn][mx]+f[r+1][k])$$

• 注意到第一个转移是填表，第二个转移是刷表

• 于是将第二个转移稍微变化一下变化成

$$g[l][r][mn][mx]=min(g[l][k][mn][mx]+f[k+1][r])$$

• 再在区间DP枚举$len$时从1开始枚举即可

---

三、代码

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,a,b,w[N],f[N][N],g[N][N][N][N],d[N];
int tot;
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]),d[i]=w[i];
	sort(d+1,d+n+1);tot=unique(d+1,d+n+1)-d-1;
	for(int i=1;i<=n;++i) w[i]=lower_bound(d+1,d+tot+1,w[i])-d,f[i][i]=a;
	memset(g,0x3f,sizeof(g));memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)g[i][i][w[i]][w[i]]=0;
	for(int len=1;len<=n;++len)
		for(int l=1,r=len;r<=n;++l,++r)
			for(int mn=1;mn<=tot;++mn)
				for(int mx=mn;mx<=tot;++mx){
					int &G=g[l][r][mn][mx];
					for(int k=l;k<r;++k)	G=min(g[l][k][mn][mx]+f[k+1][r],G);
					int &gg=g[l][r+1][min(mn,w[r+1])][max(mx,w[r+1])];
					gg=min(gg,G);f[l][r]=min(f[l][r],G+a+b*(d[mx]-d[mn])*(d[mx]-d[mn]));
				}
	printf("%d\n",f[1][n]);
}