开发者社区> 华山青竹> 正文

最佳加法表达式

简介: 最佳加法表达式 总时间限制: 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

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23541 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22268 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19088 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
11984 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22189 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36371 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14705 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载