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

code

6 年前

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

时间： 1ms 内存：64M

描述：

有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36

输入：

有不超过15组数据
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=17)
第二行是若干个数字。数字总数n不超过18,且 m <= n-1

输出：

对每组数据，输出最小加法表达式的值

示例输入：

示例输出：

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;
}

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