自动搬运

查看原文

来自洛谷，原作者为

	Hasinon www

搬运于2025-08-24 22:24:56，当前版本为作者最后更新于2021-08-04 20:11:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

（第一次发题解，做的不好请多谅解)

而且题目有点小错误，粗体表示大小关系的词都应该是小于等于。

首先我们要探讨下如何得到每一个有质量的算术表达式的最大值

'+' 组成的表达式简单
一个由 '+' 组成的表达式: $X=(x_1 + x_2 + ... + x_n)$
表达式 X 最大值就是所有被包含表达式 $x$ 的最大值的和与当前表达式的限制最大值 $z_n$的最大值

'* ' 组成的表达式，就要涉及均值不等式了。

均值不等式的一部分是几何平均数小于等于算术平均数
即：$\sqrt[n]{x_1 \times x_2 \times...\times x_n } \le \frac{1}{n}\sum_{i=1}^nx_i $
所以 ：$ x_1 \times x_2 \times...\times x_n \le (\frac{1}{n}\sum_{i=1}^nx_i)^n $

一个由 '* ' 组成的表达式: $X=(x_1 * x_2 * ... * x_n)$的值就是左式
所以表达式 $X$ 最大值等于所有被包含表达式 $x$ 的最大值的平均数的n次方.

但是吧，这是理想情况，实际会出现某被包含表达式 $x$ 的最大值小于平均数的情况。

这时先单独把答案乘上这项的最大值，把平均数与最大值之差除以剩下的数的数量再加到平均数上。 （也能用均值不等式证明最优）

还会出现刚开始某被包含表达式 $x$ 的最大值大于等于平均数，但后面随着平均数的改变导致最大值小于平均数了，所以开个 while 循环执行到以上情况不出现就好。
（忘记考虑这个了，因此考试时丢了 10 分呜呜）

实现的话用 DFS 做：
每一个 DFS 返回的是此表达式的最大值。

遇到 '(' 就往下一层。

遇到 '?' 就...其实不用管的啦，因为每个 '?' 都是被一队括号圈起来的，只要只检查到括号，没有 '+' 和 '* ' ,肯定只有一个 '?' ,就是只有一个被包含表达式 $x$ ,所以返回$z_1$

遇到 '+' 或者 '* ' 记录一下。

遇到 ')'就算出此表达式最大值，然后返回。

(注意一下输入啊，第一行后面有个空格)

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
double z[55];
ll a[100005],ato=0;
double dfs()
{
	ll t=-1;//如果没有 '+','*'，直接返回只有一个问号的时候的最大值z[1]
	ll num=0;
	vector<double> bds;
	char c;
	while(1){ 
		c=getchar();
		if(c=='(') 
		{
			bds.push_back(dfs());//遇 '(' 进下一层
			num++;
		} 
		else{
			if(c=='+') t=0;//记录
			else{
				if(c=='*') t=1;//记录
				else{
					if(c==')')//开始算最大值
					{
						if(t==0)
						{
							double tot=0;
							for(int i=0; i<num; i++)
								tot+=bds[i]; 
							return min(tot,z[num]);
						}
						else
						{
							if(t==1)
							{
							double lnum=num,aver=z[num]/lnum,tot=1,dtaver=0;
							ato=0;
							for(int i=0; i<num; i++)
							a[++ato]=i;
							while(1)//不断判断是否存在某表达式最大值小于平均数并改变平均数
							{
								bool lb=0;
								ll lato=ato;
								ato=0;
								for(int j=1; j<=lato; j++)
								{
									ll i=a[j];
									if(bds[i]<aver) 
									{
										tot*=bds[i];
										dtaver=dtaver+(aver-bds[i]);
										lnum--; 
										lb=1;
									}
									else
									{
										a[++ato]=i;
									}
								}
								if(lb==0||lnum<=0) break;
								dtaver/=lnum;
								aver+=dtaver;
								dtaver=0;
							}
							if(lnum>0)//剩下的数直接按平均数乘就好
							{
								dtaver/=lnum;
								aver+=dtaver;
								for(int i=1; i<=lnum; i++)
								{
									tot*=aver; 
								}
							}
							return tot;
							}
							else
							{
								return z[1];//直接返回 z[1]
							}
						}
					} 
				}
			}		
		} 
	}
}
int main()
{
	ll k;
	cin>>k;
	for(int i=1; i<=k; i++)
		cin>>z[i];
	char lc=getchar();
	while(lc!='(') lc=getchar();
	printf("%.6f", dfs());//%.6f 保留 6 位小数
}