题目描述
有一个由1..9组成的数字串.问如果将m个加 号插入到这个数字串中,在各种可能形成的 表达式中,值最小的那个表达式的值是多少 。例如,在1234中摆放1个加号,最好的摆法就是12+34,和为36
输入
有不超过15组数据
每组数据两行。第一行是整数m,表示有m个加号要放( 0<=m<=17)
第二行是若干个数字。数字总数n不超过18,且 m <= n-1
输出
对每组数据,输出最小加法表达式的值
样例输入
2
123456
1
123456
4
12345
样例输出
102
579
15
参考代码
#include<stdio.h>
#include<string.h>
char ch[20];
int a[20],sum=0,t,n;
int b[20];
long long int max=9223372036854775807;
void f(int ,int);
long long int init();
long long int put(int ,int );
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",ch);
if(n==0)
{
printf("%sn",ch);
continue;
}
for(i=0;i<20;i++)
a[i]=0;
for(i=0;i<strlen(ch);i++)
a[i]=ch[i]-'0';
t=strlen(ch);
f(0,0);
printf("%lldn",max);
max=9223372036854775807;
}
return 0;
}
void f(int x,int flag)
{
int i;
long long int y;
if(x==n)
{
y=init();
if(y<max)
max=y;
return;
}
for(i=flag+1;i<t;i++)
{
b[x]=i;
f(x+1,i);
}
}
long long int init()
{
int i;
long long int count=0;
for(i=0;i<n+1;i++)
{
if(i==0)
{
count=count+put(1,b[i]);
continue;
}
if(i==n)
{
count=count+put(b[i-1]+1,t);
continue;
}
count=count+put(b[i-1]+1,b[i]);
}
return count;
}
long long int put(int x,int y)
{
int i,d=y-x;
long long int count=0,c=1;
for(i=0;i<d;i++)
c=c*10;
for(i=x;i<=y;i++)
{
count=count+a[i-1]*c;
c=c/10;
}
return count;
}
解析
暂无