OpenJudge 4152 最佳加法表达式

总时间限制: 1000ms 内存限制: 65536kB

描述

给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36

输入

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

输出

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

样例输入

样例输出

提示

要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。

解题思路

主要难点在高精度计算，以下提供两种解法，码着日后研究。

AC代码一

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

struct BigInt

{

    int num[];

    int len;

    BigInt operator+(const BigInt & n) { //重载+，使得 a + b在 a,b都是 BigInt变量的时候能成立

        int ml = max(len,n.len);

        int carry = ; //进位

        BigInt result;

        for(int i = ;i < ml; ++i) {

            result.num[i] = num[i] + n.num[i] + carry;

            if( result.num[i] >= )     {

                carry = ;

                result.num[i] -= ;

            }

            else

                carry = ;

        }

        if ( carry == ) {

            result.len = ml + ;

            result.num[ml] = ;

        }

        else

            result.len = ml;

        return result;

    }

    bool operator<(const BigInt & n) {

        if( len > n.len )

            return false;

        else if( len < n.len)

            return true;

        else {

            for(int i = len -; i >= ; -- i) {

                if( num[i] < n.num[i])

                    return true;

                else if( num[i] > n.num[i])

                    return false;

            }

            return false;

        }

    }

    BigInt() {

        len = ;

        memset(num,,sizeof(num));

    }

    BigInt(const char * n,int L) { //由长度为L的char数组构造大整数。n里面的元素取值范围从 1-9。

        memset(num,,sizeof(num));

        len = L;

        for(int i = ; n[i]; ++i)

            num[len-i-] = n[i] - '';

    }

};

ostream & operator <<(ostream & o,const BigInt & n)

{

    for(int i = n.len - ;i >= ; --i)

        o << n.num[i];

    return o;

}

const int MAXN  = ;

char a[MAXN];

BigInt Num[MAXN][MAXN];//Num[i][j]表示从第i个数字到第j个数字所构成的整数

BigInt V[MAXN][MAXN]; //V[i][j]表示i个加号放到前j个数字中间，所能得到的最佳表达式的值。

int main()

{

    int m,n;

    BigInt inf; //无穷大

    inf.num[MAXN-] = ;

    inf.len = MAXN-;

    while(cin >> m ) {

        cin >> a+;

        n = strlen(a+);

        for(int i = ;i <= n; ++i)

            for(int j = i;j<= n; ++j) {

                Num[i][j] = BigInt(a+i,j-i+);

            }

        for(int j = ; j <= n; ++j)  {

            V[][j] = BigInt(a+,j);

        }

        for(int i = ;i <= m; ++i) {

            for(int j = ; j <= n; ++j) {

                if( j -  < i)

                    V[i][j] = inf;

                else {

                    BigInt tmpMin = inf;

                    for(int k = i; k < j; ++k) {

                        BigInt tmp = V[i-][k] + Num[k+][j];

                        if (tmp < tmpMin)

                            tmpMin = tmp;

                    }

                    V[i][j] = tmpMin;

                }

            }

        }

        cout << V[m][n] << endl;

    }

    return ;

}

AC代码二

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#include <set>

#include <map>

#include <list>

#include <vector>

#include <stack>

#define mp make_pair

//#define P make_pair

#define MIN(a,b) (a>b?b:a)

//#define MAX(a,b) (a>b?a:b)

typedef long long ll;

typedef unsigned long long ull;

const int MAX=1e2+;

const int INF=1e8+;

using namespace std;

//const int MOD=1e9+7;

typedef pair<ll,int> pii;

const double eps=0.00000001;

string add(string x,string y)

{

    string re;

    int jin=;

    for(int i=x.length()-,j=y.length()-;i>=||j>=;i--,j--)

    {

        re=" "+re;

        re[]=(i>=?x[i]-'':)+(j>=?y[j]-'':)+jin;

        if(re[]>=)

            jin=,re[]=(re[]%)+'';

        else

            jin=,re[]=re[]+'';

    }

    if(jin)

        re=''+re;

    return re;

}

string mins(string x,string y)

{

    if(x.length()<y.length())

        return x;

    else if(y.length()<x.length())

        return y;

    else return x<y?x:y;

}

int m;

string x;

string dp[][];

int main()

{

    while(~scanf("%d",&m))

    {

        cin>>x;

        int len=x.length();

        x=" "+x;

        for(int i=;i<=len;i++)

            dp[i][]=x.substr(,i);

        for(int j=;j<=m;j++)

            for(int i=j+;i<=len;i++)

                for(int s=j;s<i;s++)

                {

                    if(s==j)

                        dp[i][j]=add(dp[s][j-],x.substr(s+,i-s));

                    else

                        dp[i][j]=mins(dp[i][j],add(dp[s][j-],x.substr(s+,i-s)));

                }

        cout<<dp[len][m]<<"\n";

    }

}

参考网址

https://blog.csdn.net/qq_43472263/article/details/88652211

https://www.cnblogs.com/huashanqingzhu/p/8097787.html

巴特西

OpenJudge 4152 最佳加法表达式

最新文章

热门文章