3139: 动态规划进阶题目之最佳加法表达式

题目描述

有一个由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;
}

解析

暂无