CF E. Vanya and Brackets(添加一对括号使得表达式的值最大)
E. Vanya and Bracketstime limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vanya is doing his maths homework. He has an expression of form ,
where x1, x2, ..., xn are
digits from 1 to 9, and signrepresents
either a plus '+' or the multiplication sign '*'. Vanya needs
to add one pair of brackets in this expression so that to maximize the value of the resulting expression.
Input
The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is
odd), its odd positions only contain digits from 1 to 9,
and even positions only contain signs + and * .
The number of signs * doesn't exceed 15.
Output
In the first line print the maximum possible value of an expression.
Sample test(s)
input
3+5*7+8*4
output
303
input
2+3*5
output
25
input
3*4*5
output
60
Note
Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.
Note to the second sample test. (2 + 3) * 5 = 25.
Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int N = 5005;
#define LL __int64
char fh,s;//����ջ�����ʽ
LL num; //����ջ
int ftop,ntop ,slen; //����ջ��������ջ��
void calculate(){
if(fh=='+')
num+=num,ntop--;
else if(fh=='-')
num-=num,ntop--;
else if(fh=='*')
num*=num,ntop--;
else if(fh=='/')
num/=num,ntop--;
ftop--;
}
void countfuction(int l,int r){
ftop=0;ntop=0;
int flagNum=0;
LL ans=0;
for(int i=0; i<=slen; ++i){
if(i!=slen&&(s>='0'&&s<='9')){
ans=ans*10+s-'0';
flagNum=1;
}
else{
if(flagNum)num[++ntop]=ans; flagNum=0;ans=0;
if(i==slen)break;
if(s=='+'||s=='-'){
while(ftop&&fh!='(') calculate();
fh[++ftop]=s;
}
else if(s=='*'&&i==r){
while(ftop&&fh!='(') calculate(); ftop--;
while(ftop&&(fh=='*'||fh=='/')) calculate();
fh[++ftop]=s;//printf("# ");
}
else if(s=='*'||i==l){
while(ftop&&(fh=='*'||fh=='/')) calculate();
fh[++ftop]=s;
if(i==l)
fh[++ftop]='(';
}
}
}
while(ftop) calculate();
}
int main(){
while(scanf("%s",s)>0){
LL ans=0;
int id,k=0;
for(int i=strlen(s); i>=0; i--)
s=s;
s='1'; s='*';
slen=strlen(s);
s='*'; s='1'; s='\0';
slen=strlen(s);
for(int i=0; i<slen; i++)
if(s=='*')
id=i;
for(int i=0; i<k-1; i++)
for(int j=i+1; j<k; j++){
countfuction(id,id);
if(num>ans)
ans=num;
}
printf("%I64d\n",ans);
}
}
页:
[1]