自动搬运

查看原文

来自洛谷，原作者为

	nothingness **

搬运于2025-08-24 21:24:31，当前版本为作者最后更新于2018-06-17 00:37:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一篇正确的c++题解

题外话:本人提供了hack数据(第11组)后原来的4篇题解有3篇是不能AC的,我来发一下自认为比较合理的代码

正题:

首先,这题是区间dp; 其次, $n=15$ 的数据告诉我们这题其实可以暴力枚举乘号的位置, 然后,然后就能做了......

(我个人认为 "用 $f[i][j]$ 表示前 $i$ 个数插 $j$ 个乘号的最优解" 会更好,但是如果用这样的方法都有反例,会被hack掉,但是笔者的水平有限,没有发现这种方法的问题所在,请发现问题或者有更优解的读者通过私信我的方式或在旁边评论进行斧正,谢谢)

还有,我觉得第7个点的正确答案是5040,但是答案却是252(开始是0,后来变成了252),不知道是我的问题还是数据的锅,欢迎各位读者前来探讨(本文发布于2018.6.17,文章采用此时数据)

Code

#include "bits/stdc++.h"
#define cal(x,y,t) (t==1?x+y:x*y)//根据xy之间的符号进行计算
#define ll long long
using namespace std;

ll ans=-1,f[16][16];//f[i][j]表示第i个数到第j个数的最大值
int n,k,s[15],a[16];
//s[i]标记符号,若为1,表示a[i]和a[i+1]之间为加号,为2则是乘号

ll dp()//确定所有符号后dp求最值
{
	for(int i=1;i<=n;i++)
		f[i][i]=a[i];//初始化
	int j;
    //区间dp模板
	for(int l=1;l<=n;l++)//长度
		for(int i=1;i+l-1<=n;i++)//左端点
		{
			j=i+l-1;//右端点
			for(int k=i;k<j;k++)
				f[i][j]=max(f[i][j],cal(f[i][k],f[k+1][j],s[k]));
                //取原数或合并后的数的较大值
		}
	return f[1][n];//f[1][n]即为所求的一个解
}

int dfs(int x,int t1,int t2)//深搜确定乘号位置
{
	if(x==n)
	{
		memset(f,0,sizeof(f));//多次判断,记得清空数组
		ans=max(ans,dp());
		return 0;
	}
    //其实一个参数就够了,笔者这里还可以优化,不过这样方便理解
	if(t1<k)//枚举乘号
	{
		s[x]=2;
		dfs(x+1,t1+1,t2);
	}
	if(t2<n-k-1)//枚举加号
	{
		s[x]=1;
		dfs(x+1,t1,t2+1);
	}
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dfs(1,0,0);//深搜确乘号位置
	printf("%lld",ans);
	return 0;
}