@chen_zhe

题目链接

这道题目第七个点n=12 k=10(就是说有10个乘号，有且仅有1个加号)

第二行的前两个数是4和9(我通过输出前5个字符得到的数据)

题目的期望答案是0

但是根据我已经得到的数据，只要第一个数和第二个数之间放加号，其他地方放乘号，答案就不可能是0，并且4>0(尽管4不是最优解)，答案显然错误。

求管理员大大验证一下是否有错，谢谢！

附90分代码：

#include "bits/stdc++.h"
#define max(x,y) (x>y?x:y)
#define cal(x,y,t) (t==1?x+y:x*y)
#define ll long long
using namespace std;

ll ans=-1,f[16][16];
int n,k,s[15],a[16];

ll dp()
{
	for(int i=1;i<=n;i++)
		f[i][i]=a[i];
	int j;
	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];
}

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;
}