若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

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

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,296

题目描述

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

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist