问题标题: 酷町堂:4938

0
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->算术结果最小值
我要回答