E. Vanya and Brackets time 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 sign
represents 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).
給你一個表達式,隻有乘号和加号,數字都是1到9,要求加一個括号,使得表達式的值最大,問最大是多少。乘号個數<=15。
左括号一定在乘号右邊,右括号一定在乘号左邊,因為如果不是這樣的話,一定可以調整括号的位置使表達式的值增大。這個應該不難想。
于是隻要枚舉括号的位置然後計算表達式即可。
轉載請注明出處:尋找&星空の孩子
題目連結:http://codeforces.com/contest/552/problem/E
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int N = 5005;
#define LL __int64
char fh[N],s[N];
LL num[N];
int ftop,ntop ,slen;
void calculate(){
if(fh[ftop]=='+')
num[ntop-1]+=num[ntop],ntop--;
else if(fh[ftop]=='-')
num[ntop-1]-=num[ntop],ntop--;
else if(fh[ftop]=='*')
num[ntop-1]*=num[ntop],ntop--;
else if(fh[ftop]=='/')
num[ntop-1]/=num[ntop],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[i]>='0'&&s[i]<='9')){
ans=ans*10+s[i]-'0';
flagNum=1;
}
else{
if(flagNum)num[++ntop]=ans; flagNum=0; ans=0;
if(i==slen)break;
if(s[i]=='+'||s[i]=='-'){
while(ftop&&fh[ftop]!='(') calculate();
fh[++ftop]=s[i];
}
else if(s[i]=='*'&&i==r){
while(ftop&&fh[ftop]!='(') calculate(); ftop--;
while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
fh[++ftop]=s[i];//printf("# ");
}
else if(s[i]=='*'||i==l){
while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
fh[++ftop]=s[i];
if(i==l)
fh[++ftop]='(';
}
}
}
while(ftop) calculate();
}
int main(){
while(scanf("%s",s)>0){
LL ans=0;
int id[20],k=0;
for(int i=strlen(s); i>=0; i--)
s[i+2]=s[i];
s[0]='1'; s[1]='*';
slen=strlen(s);
s[slen]='*'; s[slen+1]='1'; s[slen+2]='\0';
slen=strlen(s);
for(int i=0; i<slen; i++)
if(s[i]=='*')
id[k++]=i;
for(int i=0; i<k-1; i++)
for(int j=i+1; j<k; j++){
countfuction(id[i],id[j]);
if(num[1]>ans)
ans=num[1];
}
printf("%I64d\n",ans);
}
}
或着
#include <bits/stdc++.h>
using namespace std;
int n;
string str;
vector<int> pos;
stack<char> sc;
stack<long long> sn;
long long twoResult(long long a, long long b, char c) {
return (c == '*') ? a * b : a + b;
}
void cal() {
char t = sc.top();
sc.pop();
long long a = sn.top();
sn.pop();
long long b = sn.top();
sn.pop();
sn.push(twoResult(a, b, t));
}
long long expression(string s) {
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (isdigit(c)) {
sn.push(c - '0');
} else if (c == '(') {
sc.push(c);
} else if (c == ')') {
while (sc.top() != '(')
cal();
sc.pop();
} else {
if (c == '+') {
while (!sc.empty() && sc.top() == '*')
cal();
sc.push(c);
} else sc.push(c);
}
}
while (!sc.empty()) cal();
return sn.top();
}
int main() {
cin >> str;
n = str.size();
pos.push_back(-1);
for (int i = 1; i < n; i += 2)
if (str[i] == '*') pos.push_back(i);
pos.push_back(n);
int len = pos.size();
long long ans = 0;
for (int i = 0; i < len - 1; i++) { // left
for (int j = i + 1; j < len; j++) { // right
string s = str;
s.insert(pos[i] + 1, 1, '(');
s.insert(pos[j] + 1, 1, ')');
ans = max(ans, expression(s));
}
}
cout << ans << endl;
return 0;
}