[HDOJ5938]Four Operations（暴力，DFS）

题目链接：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 ;

 }

巴特西

[HDOJ5938]Four Operations（暴力，DFS）

最新文章

热门文章