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

时间: 1ms        内存:64M

描述:

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

提示:

参考答案(内存最优[1092]):

#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("%s\n",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("%lld\n",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;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m,ls;
char s[20];
long sum1;
long long a[20][20];
void DFS(int m,int y,long long  sum)
{
    if(m==0)
    {
        sum+=a[ls-1-y][y];
        if(sum<sum1)
            sum1=sum;
        return;
    }
    for(int i=0;i<ls-y;i++)
    {
        sum+=a[i][y];
        DFS(m-1,y+1+i,sum);
        sum-=a[i][y];
    }
}
int main()
{
    while(scanf("%d %s",&m,s)!=EOF)
    {
        ls=strlen(s);
        memset(a,0,sizeof(a));
        if(m==0)
        {
            printf("%s\n",s);
            continue;
        }
        for(int i=0,la=0;i<ls;i++)
        {
            for(int j=0;j<ls-i;j++)
                a[i][j]+=s[j+la]-'0';
            la++;
            for(int j=0;j<ls-la;j++)
                a[i+1][j]=a[i][j]*10;
        }
        sum1=2147483647;
        DFS(m,0,0);
        printf("%ld\n",sum1);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。