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。
左括号一定在乘号右边，右括号一定在乘号左边，因为如果不是这样的话，一定可以调整括号的位置使表达式的值增大。这个应该不难想。
于是只要枚举括号的位置然后计算表达式即可。
转载请注明出处：寻找&星空の孩子
题目链接：
#include<stdio.h>#include<iostream>#include<string.h>#include<math.h>using namespace std;const int N = 5005;#define LL __int64char 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++) { // leftfor (int j = i + 1; j < len; j++) { // rightstring s = str;s.insert(pos[i] + 1, 1, '(');s.insert(pos[j] + 1, 1, ')');ans = max(ans, expression(s));}}cout << ans << endl;return 0;}
把自己当傻瓜，不懂就问，你会学的更多
