最佳加法表达式-阿里云开发者社区

最佳加法表达式

总时间限制: 1000ms 内存限制: 65536kB

描述

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

输入

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

输出

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

样例输入

样例输出

102
579
15

提示

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

算法参考：http://www.cnblogs.com/quintessence/p/7206417.html 使用了高精度

http://www.cnblogs.com/Renyi-Fan/p/6970166.html 没有使用高精度，有详细分析

假定数字串长度是n，添完加号后,表达式的最后一个加号添加在第 i 个数字后面，
那么整个表达式的最小值，就等于在前 i 个数字中插入 m – 1个加号所能形成的最小值，
加上第 i + 1到第 n 个数字所组成的数的值（i从1开始算）。

设V(m,n)表示在n个数字中插入m个加号所能形成
的表达式最小值，那么：
if m = 0
V(m,n) = n个数字构成的整数
else if n < m + 1
V(m,n) = ∞
else
V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)
Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操作复杂度是O(j-i+1)
总时间复杂度：O(mn²) .（dp二维表已经加号的位置）

 1 #include<iostream>
 2 #include<cstdio> 
 3 #include<cstring> 
 4 #include<algorithm> 
 5 using namespace std;
 6 const int INF=0x3f3f3f3f;
 7 const int N=1005;
 8 int a[N],num[N][N],dp[N][N];
 9 //a[N]里面是存数字串
10 //num[i][j]表示数字串a[N]的第i位到第j位之间的数字串表示的数组
11 //dp[i][j]在i个数字中插入j个加号所能形成的表达式最小值
12 int main(){
13     int n,m;
14     while(scanf("%d %d",&n,&m)){
15         for(int i=1;i<=n;i++){
16             scanf("%d",&a[i]);
17         }
18         //预处理,计算i到j数字串组成的数字 
19         for(int i=1;i<=n;i++){
20             num[i][i]=a[i];//只有一个数字 
21             for(int j=i+1;j<=n;j++){
22                 num[i][j]=num[i][j-1]*10+a[j];
23             } 
24         }
25         memset(dp,0x3f,sizeof(dp));
26         for(int i=1;i<=n;i++){
27             dp[0][i]=num[1][i];//无加号时 
28         }
29         //其实就是感觉在那个位置放不放加号 
30         //这里n可以写在m前面。要加一个限制条件n>m，好麻烦，所以m在前且n=m+1
31         //这里k的取值范围就是m到n，k表示在第k个数后面插入加号 
32         for(int i=1;i<=m;i++)
33             for(int j=i;j<=n;j++)
34                 for(int k=i;k<=j;k++)
35                     dp[i][j]=min(dp[i][j],dp[i-1][k]+num[k+1][j]); 
36         cout<<dp[m][n]<<endl; 
37     }
38 }

未使用高精度的代码

下面是使用了高精度数据结构的算法代码：

首先，由于数据范围显然需要用到高精度，高精度的写法不再赘述。

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位组成的数。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 #include <set>
 9 #include <map>
10 #include <list>
11 #include <vector>
12 #include <stack>
13 #define mp make_pair
14 //#define P make_pair
15 #define MIN(a,b) (a>b?b:a)
16 //#define MAX(a,b) (a>b?a:b)
17 typedef long long ll;
18 typedef unsigned long long ull;
19 const int MAX=1e2+5;
20 const int INF=1e8+5;
21 using namespace std;
22 //const int MOD=1e9+7;
23 typedef pair<ll,int> pii;
24 const double eps=0.00000001;
25 
26 string add(string x,string y)
27 {
28     string re;
29     int jin=0;
30     for(int i=x.length()-1,j=y.length()-1;i>=0||j>=0;i--,j--)
31     {
32         re=" "+re;
33         re[0]=(i>=0?x[i]-'0':0)+(j>=0?y[j]-'0':0)+jin;
34         if(re[0]>=10)
35             jin=1,re[0]=(re[0]%10)+'0';
36         else
37             jin=0,re[0]=re[0]+'0';
38     }
39     if(jin)
40         re='1'+re;
41     return re;
42 }
43 string mins(string x,string y)
44 {
45     if(x.length()<y.length())
46         return x;
47     else if(y.length()<x.length())
48         return y;
49     else return x<y?x:y;
50 }
51 int m;
52 string x;
53 string dp[55][55];
54 int main()
55 {
56     while(~scanf("%d",&m))
57     {
58         cin>>x;
59         int len=x.length();
60         x=" "+x;
61         for(int i=0;i<=len;i++)
62             dp[i][0]=x.substr(1,i);
63         for(int j=1;j<=m;j++)
64             for(int i=j+1;i<=len;i++)
65                 for(int s=j;s<i;s++)
66                 {
67                     if(s==j)
68                         dp[i][j]=add(dp[s][j-1],x.substr(s+1,i-s));
69                     else
70                         dp[i][j]=mins(dp[i][j],add(dp[s][j-1],x.substr(s+1,i-s)));
71                 }
72         cout<<dp[len][m]<<"\n";
73     }
74 }

下面是自己写的原始高精度算法的代码，结果超时了。。。

  1 #include <stdio.h>
  2 #include<string.h>
  3 
  4 #define MaxLength 91
  5 int m,len,a[MaxLength];
  6 long long count=0;
  7 
  8 void init(char str[],int a[]);
  9 void add(int a[],int b[],int c[]);
 10 int cmp(int a[],int b[]);
 11 void fun(int m,int n,int min[]);
 12 void num(int i,int j,int t[]);
 13 void output(int minSum[]);
 14 
 15 int main(int argc, char *argv[])
 16 {
 17     freopen("003.txt","r",stdin);
 18     freopen("003.out","w",stdout);
 19     char str[MaxLength];
 20     int minSum[MaxLength];
 21     int i;
 22     
 23     while(scanf("%d%s",&m,str)!=EOF)
 24     {
 25         init(str,a);
 26         len=a[0];
 27         /*printf("%d\n",m);
 28         for(i=1;i<=a[0];i++) printf("%d",a[i]);
 29         printf("\n");*/
 30         for(i=1;i<MaxLength;i++) { minSum[i]=9; }
 31         minSum[0]=MaxLength+4;
 32         
 33         fun(m,len,minSum);
 34         output(minSum);
 35     }
 36     
 37     /*char str1[20]="1",str2[20]="234";
 38     int aa[25],bb[25],cc[25];
 39     
 40     init(str1,aa);
 41     init(str2,bb);
 42     for(int i=0;i<=aa[0];i++) printf("%d",aa[i]);printf("\n");
 43     for(int i=0;i<=bb[0];i++) printf("%d",bb[i]);printf("\n");
 44     add(aa,bb,cc);
 45     for(int i=0;i<=cc[0];i++) printf("%d",cc[i]);printf("\n");*/
 46     
 47     return 0;
 48 }
 49 
 50 /******************************************************************************/
 51 /*输入一个字符串str表示高精度正整数
 52   将str转换成int数组存储在a[]
 53   a[0]存储str代表的数字的位数
 54   str正序存储在a[]中 
 55 */
 56 void init(char str[],int a[])
 57 {
 58     int i;
 59     //memset(a,0,sizeof(int)*MaxLength);
 60     a[0]=strlen(str);
 61     for(i=1;i<=a[0];i++)
 62         a[i]=str[i-1]-'0';
 63 }
 64 /******************************************************************************/
 65 void fun(int m,int n,int min[])
 66 {
 67     int i,j,x[MaxLength]={0},y[MaxLength]={0},sum[MaxLength];
 68     //printf("m=%d n=%d\n",m,n);
 69     if(m==0)
 70     {
 71         num(1,n,min);
 72     }
 73     else if(n<m+1)
 74     {
 75         for(i=1;i<MaxLength;i++) { min[i]=9;}
 76         min[0]=MaxLength+2;
 77     }
 78     else 
 79     {
 80         for(i=0;i<MaxLength;i++) min[i]=9;
 81         min[0]=MaxLength+2;
 82         
 83         for(i=m;i<n;i++)
 84         {
 85             fun(m-1,i,x);
 86             num(i+1,n,y);
 87             add(x,y,sum);
 88             if(cmp(sum,min)==-1)
 89             {    for(j=0;j<=sum[0];j++) min[j]=sum[j];    }
 90         }
 91     }
 92 }
 93 /******************************************************************************/
 94 void num(int i,int j,int t[])
 95 {
 96     count++;
 97     //printf("%d\n",count);
 98     
 99     int k;
100     t[0]=j-i+1;
101     for(k=1;i<=j;k++,i++) t[k]=a[i];
102 }
103 /******************************************************************************/
104 /*  输入高精度正整数a和b,计算c=a+b   */
105 void add(int a[],int b[],int c[])
106 {
107     int x=0,i=a[0],j=b[0],k=1;
108     //memset(c,0,sizeof(int)*MaxLength);
109     //这个地方初始化的字节数的解释：c[]从主调函数传过来，c的元素个数未知。
110     //sizeof(c)只能测出一个元素的字节数，而不是整个数组的字节数 
111     
112     while(i>0&&j>0)
113     {
114         c[k]=a[i]+b[j]+x;//x表示加法的进位 
115         x=c[k]/10;    //新产生的进位 
116         c[k]=c[k]%10; //只保留个位 
117         k++;
118         i--;
119         j--;
120     }
121     while(i>0)
122     {
123         c[k]=a[i]+x;
124         x=c[k]/10;
125         c[k]=c[k]%10;
126         k++;
127         i--;
128     }
129     while(j>0)
130     {
131         c[k]=b[j]+x;
132         x=c[k]/10;
133         c[k]=c[k]%10;
134         k++;
135         j--;
136     }
137     c[k]=x;  //可能有向更高位的进位 
138     if(c[k]==0) k--;
139     c[0]=k;
140     
141     for(i=1,j=c[0];i<j;i++,j--)
142     {
143         x=c[i]; c[i]=c[j]; c[j]=x;
144     }
145 }
146 /******************************************************************************/
147 /*  比较a[]和b[]表示的两个高精度整数的大小，返回1表示a>b，0表示相等，-1表示a<b   */
148 int cmp(int a[],int b[])
149 {
150     int i;
151     if(a[0]<b[0]) return -1;
152     else if(a[0]>b[0]) return 1;
153     else
154     {
155         i=1;
156         while(i<=a[0]&&a[i]==b[i]) i++;
157         if(i>a[0]) return 0;
158         else if(a[i]<b[i])return -1;
159         else return 1;
160     }
161 }
162 /******************************************************************************/
163 void output(int minSum[])
164 {
165     int i;
166     for(i=1;i<=minSum[0];i++)
167     {
168         printf("%d",minSum[i]);
169     }
170     printf("\n");
171 }

View Code