【字符串处理·新定义表达式（括号处理·递归）·思维】Kvalitetni--7.2测试 COCI

样例
2
10 6
((?)+(?))6.000003
2 5 3
(((?)+(?))*(?))6.000003
2 10 6
((?)*(?)*(?))8.000000000

分析

首先，我们可以发现，这个问题是可以递归的（大多数表达式都可以递归），递归到最小的子问题的话，这个什么质量表达式本质上有三类：
$(A)$
$(A1+A2+\dots +Ak)$
$(A1\ast A2\ast \dots \ast Ak)$

第一种 就让它的值为$Z1$，就是最大的嘛

对于第二种和第三种 由于递归处理 我们先让每个数为他最大的值（递归本来就在干这件事）然后再来考虑限制的问题

第二种 我们就要考虑一下满足这$k$个数之和不超过$Zk$，也比较好处理 因为是求和，而本身限制就是和要小于等于$Zk$ 答案就是$min（Zk,A1+A2+\dots +Ak）$

第三种，是最不好处理的
首先，我们要尽可能不减小这些数，也就是说，这些数的和也要尽量保持最大 同上，我们也还是知道这$k$个数之和，为$min（Zk,A1+A2+\dots +Ak）$
可是我们要求的是乘积的最大值，又知道了和为一个定值，就可以用均值不等式得出：
这$k$个数相等的时候乘积就最大
可是我们不能暴力地把每一个数都变成$sum/k$
因为有的数的最大值$Ai$本身小于$sum/k$，取不到$sum/k$
我们就要让这些数尽量接近$sum/k$，也就是取到它自己的最大值$Ai$
但是呢
要注意的是 这些数取了$Ai$之后，其它数就不能再取原来的$sum/k$ 因为：这个数既然确定，我们就去掉它；去掉这一个数之后剩下的那些数要再取乘积最大，显然之前的$sum/k$已经不是剩下那些数的均值 使他们乘积最大的均值应该还要大一些（去掉了一个较小数

所以我们就要重新求这个均值：把取了$Ai$的数去掉，再求剩下的数的均值

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector> 
using namespace std;
#define LL long long
#define MAXN 1000005
#define INF 0x3f3f3f3f
int k;
int z[55],p[MAXN];
char s[MAXN];
stack<int>S;
double work(int l,int r)
{if(l+2==r) return (double)z[1];//只有一个数,先把它搞成最大,然后再考虑符不符合Sum<=z[k] bool f;//1: + ; 0: *vector<double>V;//当前这个区间包含的数 for(int i=l+1;i<r;i++){if(s[i]=='+') f=1;if(s[i]=='*') f=0;if(s[i]=='('){V.push_back(work(i,p[i]));i=p[i];//跳到下一个递归区间 }}double ans;if(f){//处理连+的情况 ans=0;for(int i=0;i<V.size();i++)ans+=V[i];ans=min(ans,(double)z[V.size()]);}else{ans=1;sort(V.begin(),V.end());double sum=z[V.size()];//最大的和 for(int i=0;i<V.size();i++){//尽量取到平均值 如果取不到那么大 小的数就尽量取大 然后平均值就会变化 double tmp=sum/(V.size()-i);if(V[i]>=tmp)//如果最小的那一堆数取不到平均水平，就尽可能接近平均水平 sum-=tmp,ans*=tmp;else sum-=V[i],ans*=V[i];}}return ans;
}
int main()
{freopen("kvalitetni.in","r",stdin);freopen("kvalitetni.out","w",stdout);scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%d",&z[i]);scanf("%s",s+1);int len=strlen(s+1);for(int i=1;i<=len;i++){if(s[i]=='(')S.push(i);if(s[i]==')'){int pos=S.top();S.pop();p[pos]=i;//记录左括号对应的右括号位置 }}printf("%.3f\n",work(1,len));return 0;
}