011:最佳加法表达式

总时间限制: 

1000ms 

内存限制: 

65536kB

描述

给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36

输入

有不超过15组数据

每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)

第二行是若干个数字。数字总数n不超过50,且 m <= n-1

输出

对每组数据，输出最小加法表达式的值

样例输入

21234561123456412345

样例输出

10257915

提示

要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。

来源

Guo Wei

解题思路

代码

#include
        
           #include
         
            #include
          
             using namespace std;  const int MaxLen = 55;  const string maxv = "999999999999999999999999999999999999999999999999999999999";  string ret[MaxLen][MaxLen];  string num[MaxLen][MaxLen];  int cmp(string &num1,string &num2)  {
              int l1 = num1.length();      int l2 = num2.length();      if (l1 != l2)      {
                  return l1-l2;      }      else      {
                  for (int i=l1-1; i>=0; i--)          {
                      if (num1[i]!=num2[i])              {
                          return num1[i]-num2[i];              }          }          return 0;      }  }  void add (string &num1,string &num2,string &num3)  {
              //加法从低位到高位相加，那么需要将字符串倒过来      int l1 = num1.length();      int l2 = num2.length();      int maxl = MaxLen,c = 0;        //c是进位标志      for (int i=0; i
           
            = l2)          {
                      t = num1[i] - '0' + c;          }          else if (i >= l1 && i < l2)          {
                      t = num2[i] - '0' + c;          }          else          {
                      break;          }          num3.append(1,t%10+'0');          c = t/10;      }      while (c)      {
                  num3.append(1,c%10+'0');          c /= 10;      }  }  int main()  {
              int m;                  //加号数目      string str;             //输入的字符串      while(cin >> m >> str)      {
                  //为了之后的加法计算先将这个字符串倒过来          reverse(str.begin(),str.end());          int n = str.length();          for (int i=0; i
            
             0)                      {
                                  minv = tmp;                      }                  }                  ret[i][j] = minv;              }          }          //将原先颠倒的字符串倒回来          reverse(ret[m][n].begin(),ret[m][n].end());          cout << ret[m][n] << endl;      }      return 0;  }