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

本文主要是介绍【字符串处理·新定义表达式（括号处理·递归）·思维】Kvalitetni--7.2测试 COCI，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

分析

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

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

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

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

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

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

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