自动搬运

查看原文

来自洛谷，原作者为

	Querainy Now fuck off Hang out with ur bitches

搬运于2025-08-24 22:00:38，当前版本为作者最后更新于2022-05-23 21:36:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

虽然说挺水的，但是这是我的童年阴影，所以还是写个题解吧（

直接dp。设 $g(l,r)$ 表示区间 $l,...,r$ 合并成一个点的答案，$dp(l,r,i)$ 表示区间 $l,...,r$ 分成 $i$ 段，每一段合并成一个点的答案，$g$ 的转移枚举分了多少段，$dp$ 的转移枚举最后一段。复杂度 $O(n^4)$，常数小的吓人，直接冲就过了。滚一下 $dp$，空间是 $O(n^2)$ 的。

#include<stdio.h>
#include<string.h>

inline int min(int x,int y){ return x<y?x:y; }

int n,L,R;
int dp[302][302],g[302][302];
int a[302],pre[302];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&L,&R);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i];
		memset(g,0x3f,sizeof(g));
		for(int i=1;i<=n;i++) g[i][i]=0;
		for(int l=n;l>=1;l--)
		{
			memset(dp,0x3f,sizeof(dp));
			dp[l-1][0]=0;
			for(int r=l;r<=n;r++)
			{
				for(int i=1;i<=r-l+1&&i<=R;i++)
					for(int p=r;p>=l;p--)
						dp[r][i]=min(dp[r][i],dp[p-1][i-1]+g[p][r]);
				for(int i=L;i<=R;i++) g[l][r]=min(g[l][r],dp[r][i]+pre[r]-pre[l-1]);
				dp[r][1]=min(dp[r][1],g[l][r]);
			}
		}
		printf("%d\n",g[1][n]==0x3f3f3f3f?0:g[1][n]);
	}
	return 0;
}