0
已解决
4938 数字串添加运算符经验值:800
题目描述 Description
现在给出一个长度为n的由数字组成的字符串,试往每两个数字之间添加+、-、*,可以通过()任意改变运算优先级,求出这个式子能得到的最大值。
输入描述 Input Description
一行,一个数字串s
输出描述 Output Description
一个整数,表示能得到的最大值
样例输入 Sample Input
232
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
2 * 3 * 2
完美的擦肩而过(90分):
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int p(double a,double b){
return a+b;
}
int m(double a,double b){
return a-b;
}
int c(double a,double b){
return a*b;
}
string s;
double f(int l,int r){
if(l==r){
return s[l-1]-'0';
}
int mid=(l+r)/2;
double a=f(l,mid);
double b=f(mid+1,r);
return max(p(a,b),max(m(a,b),c(a,b)));
}
int main(){
int n;
cin>>s;
n=s.size();
cout<<f(1,n);
return 0;
}
哪里错了呀,而且第8个测试点是什么呀!!!
周明轩在2020-10-19 20:24:58追加了内容
ding
周明轩在2020-10-19 20:41:19追加了内容
ding
周明轩在2020-10-21 12:46:00追加了内容
ding
0
0
0
有可能是一个大负数乘一个大负数得到结果最大值
所以定义一个最小值函数
也用递推:
- int g(int l,int r){
- int ans=0x3f3f3f3f;
- if(l==r) return num[l];
- for(int i=l;i<r;i++){
- ans=min(ans,cal2(f(l,i),f(i+1,r)));
- ans=min(ans,cal2(f(l,i),g(i+1,r)));
- ans=min(ans,cal2(g(l,i),f(i+1,r)));
- ans=min(ans,cal2(g(l,i),g(i+1,r)));
- }
- return ans;
- }
- cal2->算术结果最小值