题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5938
题意：给出一个长度最大是2020的数字串, 你要把数字串划分成55段, 依次填入’+’, ’-’, ’*’, ’/’, 问能得到的最大结果。
想让这个结果最大，那尽可能让减号左边的数最大，只需要关心左边的第一位是一个数还是最后一位是一个数，后面的枚举*和/的位置就行了。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
LL ret, dret;
int n;
char s[maxn]; void dfs(int pos, int cnt, LL c, LL d, LL e) {
if(pos >= n) return;
if(cnt == ) {
dret = min(dret, c * d / e);
return;
}
if(cnt == ) {
LL tmp = ;
for(int i = pos; i < n; i++) {
tmp *= ; tmp = tmp + s[i] - '';
dfs(i+,cnt+, tmp,d,e);
}
}
if(cnt == ) {
LL tmp = ;
for(int i = pos; i < n; i++) {
tmp *= ; tmp = tmp + s[i] - '';
dfs(i+,cnt+,c,tmp,e);
} }
if(cnt == ) {
LL tmp = ;
for(int i = pos; i < n; i++) {
tmp *= ; tmp = tmp + s[i] - '';
}
dfs(-,cnt+,c,d,tmp);
}
} int main() {
// freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
scanf("%s", s);
n = strlen(s);
ret = -((LL) << );
for(int i = ; i < n-; i++) {
LL x = ;
LL y = ;
LL s1 = , s2 = , ss = ;
int j = ;
while(j < i) {
x *= ;
x = x + s[j++] - '';
}
y = s[i] - '';
s1 = x + y;
j = ;
x = s[] - ''; y = ;
while(j <= i) {
y *= ;
y = y + s[j++] - '';
}
s2 = x + y;
ss = max(s1, s2);
dret = (LL) << ;
dfs(i+, , , , );
ret = max(ret, ss-dret);
}
printf("Case #%d: ", _++);
printf("%I64d\n", ret);
}
return ;
}