被驳回两次后修改了的题解

· · 题解

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

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

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

'+' 组成的表达式简单
一个由 '+' 组成的表达式: 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 位小数
}