最佳加法表达式

Descriptions:

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

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input

有不超过15组数据 
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50) 
第二行是若干个数字。数字总数n不超过50,且 m <= n-1

Output

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

Sample Input

2

123456

1

123456

4

12345

Sample Output

102

579

15

Hint

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

题目链接：

https://vjudge.net/problem/OpenJ_Bailian-4152

 

 dp[i][j]表示前i个数添加了j个加号得到的最小和。转移方程为 dp[i][j]=min(dp[x][j-1]+num[x+1][i]) 其中x>=j且x<i num[x+1][i]表示第x+1位到第i位组成的数。可能难理解，别光看，举个例子在纸上画画试试，有助于理解

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #include <sstream>
15 #define ME0(X) memset((X), 0, sizeof((X)))
16 using namespace std;
17 const int L=100;
18 string dp[100][100];
19 string add(string a,string b)//只限两个非负整数相加
20 {
21     string ans;
22     int na[L]= {0},nb[L]= {0};
23     int la=a.size(),lb=b.size();
24     for(int i=0; i<la; i++)
25         na[la-1-i]=a[i]-'0';
26     for(int i=0; i<lb; i++)
27         nb[lb-1-i]=b[i]-'0';
28     int lmax=la>lb?la:lb;
29     for(int i=0; i<lmax; i++)
30         na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
31     if(na[lmax])
32         lmax++;
33     for(int i=lmax-1; i>=0; i--)
34         ans+=na[i]+'0';
35     return ans;
36 }
37 string mins(string a,string b)//判断大小
38 {
39     if(a.length()<b.length())
40         return a;
41     else if(b.length()<a.length())
42         return b;
43     else
44         return a<b?a:b;
45 }
46 int main()
47 {
48     int m;
49     string s;
50     while(cin >> m >> s)
51     {
52         s=" "+s;
53         int len=s.length();
54         for(int i=0; i<=len; i++)
55             dp[i][0]=s.substr(1,i);
56         for(int j=1; j<=m; j++)
57         {
58             for(int i=0; i<=len; i++)
59             {
60                 for(int x=j; x<i; x++)
61                 {
62 ////                  前x个数和"+"相等时，显然不成立，x个数最多有x-1个"+"，所以要单独处理
63                     if(x==j)
64                         dp[i][j]=add(dp[x][j-1],s.substr(x+1,i-x));
65 //                    其他的情况，状态转移方程即可
66                     else
67                         dp[i][j]=mins(dp[i][j],add(dp[x][j-1],s.substr(x+1,i-x)));
68                 }
69             }
70         }
71         cout << dp[len][m] << endl;
72     }
73 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄