最佳加法表达式

简介: 最佳加法表达式总时间限制: 1000ms 内存限制: 65536kB描述给定n个1到9的数字,要求在数字之间摆放m个加号(加号两边必须有数字),使得所得到的加法表达式的值最小,并输出该值。例如,在1234中摆放1个加号,最好的摆法就是12+34,和为36输入有不超过15组数据每组数据两行。

最佳加法表达式

总时间限制: 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 都装不下的大整数,并用模拟列竖式的办法进行大整数的加法。

 

算法参考: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(mn2) .(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

 

相关文章
|
7月前
|
存储 编译器 C语言
【表达式求值】整型提升和算术转换
【表达式求值】整型提升和算术转换
54 0
|
6月前
|
C++
C++一分钟之-理解C++的运算符与表达式
【6月更文挑战第18C++的运算符和表达式构成了编程的基础,涉及数学计算、逻辑判断、对象操作和内存管理。算术、关系、逻辑、位、赋值运算符各有用途,如`+`、`-`做加减,`==`、`!=`做比较。理解运算符优先级和结合律至关重要。常见错误包括优先级混淆、整数除法截断、逻辑运算符误用和位运算误解。解决策略包括明确优先级、确保浮点数除法、正确使用逻辑运算符和谨慎进行位运算。通过实例代码学习,如 `(a &gt; b) ? &quot;greater&quot; : &quot;not greater&quot;`,能够帮助更好地理解和应用这些概念。掌握这些基础知识是编写高效、清晰C++代码的关键。
40 3
运算符与表达式详解
运算符与表达式详解
|
7月前
|
SQL 存储 数据库
SQL 算术运算符:加法、减法、乘法、除法和取模的用法
存储过程是一段预先编写好的 SQL 代码,可以保存在数据库中以供反复使用。它允许将一系列 SQL 语句组合成一个逻辑单元,并为其分配一个名称,以便在需要时调用执行。存储过程可以接受参数,使其更加灵活和通用。
161 0
|
人工智能 Shell
if 运算表达式
if 运算表达式
63 1
|
编译器 C++
C++的运算符与表达式
在程序中,运算符是用来操作数据的,因此这些数据也被称为操作数,使用运算符将操作数连接而成的式子称为表达式
85 0
|
存储 算法
逆波兰表达式:计算包含括号的四则运算表达式
平时我们进行数学计算使用的常见书写方式就是中缀表达式,即每一个运算符号都位于计算数的中间,如下: (1+2)\3 而这对于计算机进行求取结果来说,并不是一个最优的方案。
123 0
|
C# 索引
C#之表达式与运算符
C#之表达式与运算符
C#运算符和表达式的简单运用
C#运算符和表达式的简单运用
|
Java
不用加减乘除做加法
不用加减乘除做加法
99 0
不用加减乘除做加法