最佳加法表达式
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36
- 输入
- 有不超过15组数据
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)
第二行是若干个数字。数字总数n不超过50,且 m <= n-1 - 输出
- 对每组数据，输出最小加法表达式的值
- 样例输入
-
2 123456 1 123456 4 12345
- 样例输出
-
102 579 15
- 提示
- 要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。
- 来源
- Guo Wei
极其坑爹的一道题！要写高精度！坑人！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include<iostream> #include<algorithm> #include<cstring> #include<string> using namespace std; int m; string numbers; int strlen_n; string store[51][51]; bool str_num_comp(const string & n1,const string & n2){//n1大为true,n2大为false if(n1.length()!=n2.length()){ return n1.length()>n2.length(); }else{ int len=n1.length(); for(int i=0;i<len;i++){ if(n1[i]!=n2[i]){ return n1[i]>n2[i]; } } return false; } } string add_number(const string & n1,const string & n2){ string result; int result_len,n3_len; result=n1; const string & n3=n2; result_len=result.length(); n3_len=n3.length(); for(int i=1;i<=n3_len;i++){ result[result_len-i]+=n3[n3_len-i]-'0'; } for(int i=result_len-1;i>0;i--){//最高位单独考虑 while(result[i]>'9'){ result[i]-=10; result[i-1]++; } } char c='0'; if(result[0]>'9'){ while(result[0]>'9'){ c++; result[0]-=10; } result.insert(0,1,c); } return result; } string min_num(int m,int left){ if(store[m][left]!="")return store[m][left]; if(m==0){ string result=""; result.append(numbers,left,strlen_n-left+1); store[m][left]=result; return result; }else if(m>strlen_n-left){ store[m][left]="99999999999999999999999999999999999999999999999999"; return "99999999999999999999999999999999999999999999999999"; }else{ string str="99999999999999999999999999999999999999999999999999"; for(int i=left;i<=strlen_n;i++){ string s=""; s.append(numbers,left,i-left+1); string s1=min_num(m-1,i+1); string s2; if(s.length()>s1.length()){ s2=add_number(s,s1); }else{ s2=add_number(s1,s); } if(str_num_comp(str,s2)){ str=s2; } } store[m][left]=str; return str; } } int main(){ ios::sync_with_stdio(false); while(cin>>m){ for(int i=0;i<=50;i++){ for(int j=0;j<=50;j++){ store[i][j]=""; } } cin>>numbers; strlen_n=numbers.length()-1; cout<<min_num(m,0)<<endl; } } |