首页 > 代码库 > [HDOJ5938]Four Operations(暴力,DFS)
[HDOJ5938]Four Operations(暴力,DFS)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5938
题意:给出一个长度最大是2020
的数字串, 你要把数字串划分成55
段, 依次填入’+’, ’-’, ’*’, ’/’, 问能得到的最大结果。
想让这个结果最大,那尽可能让减号左边的数最大,只需要关心左边的第一位是一个数还是最后一位是一个数,后面的枚举*和/的位置就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 22; 6 LL ret, dret; 7 int n; 8 char s[maxn]; 9 10 void dfs(int pos, int cnt, LL c, LL d, LL e) { 11 if(pos >= n) return; 12 if(cnt == 3) { 13 dret = min(dret, c * d / e); 14 return; 15 } 16 if(cnt == 0) { 17 LL tmp = 0; 18 for(int i = pos; i < n; i++) { 19 tmp *= 10; tmp = tmp + s[i] - ‘0‘; 20 dfs(i+1,cnt+1, tmp,d,e); 21 } 22 } 23 if(cnt == 1) { 24 LL tmp = 0; 25 for(int i = pos; i < n; i++) { 26 tmp *= 10; tmp = tmp + s[i] - ‘0‘; 27 dfs(i+1,cnt+1,c,tmp,e); 28 } 29 30 } 31 if(cnt == 2) { 32 LL tmp = 0; 33 for(int i = pos; i < n; i++) { 34 tmp *= 10; tmp = tmp + s[i] - ‘0‘; 35 } 36 dfs(-1,cnt+1,c,d,tmp); 37 } 38 } 39 40 int main() { 41 // freopen("in", "r", stdin); 42 int T, _ = 1; 43 scanf("%d", &T); 44 while(T--) { 45 scanf("%s", s); 46 n = strlen(s); 47 ret = -((LL)1 << 40); 48 for(int i = 1; i < n-3; i++) { 49 LL x = 0; 50 LL y = 0; 51 LL s1 = 0, s2 = 0, ss = 0; 52 int j = 0; 53 while(j < i) { 54 x *= 10; 55 x = x + s[j++] - ‘0‘; 56 } 57 y = s[i] - ‘0‘; 58 s1 = x + y; 59 j = 1; 60 x = s[0] - ‘0‘; y = 0; 61 while(j <= i) { 62 y *= 10; 63 y = y + s[j++] - ‘0‘; 64 } 65 s2 = x + y; 66 ss = max(s1, s2); 67 dret = (LL)1 << 40; 68 dfs(i+1, 0, 0, 0, 0); 69 ret = max(ret, ss-dret); 70 } 71 printf("Case #%d: ", _++); 72 printf("%I64d\n", ret); 73 } 74 return 0; 75 }
[HDOJ5938]Four Operations(暴力,DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。