牛客假日团队赛10 L 乘积最大（dp，大数）

链接：https://ac.nowcoder.com/acm/contest/1072/L?&headNav=acm&headNav=acm

来源：牛客网

乘积最大

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312，当N=3，K=1时会有以下两种分法：

3*12=36
312=62

这时，符合题目要求的结果是：312=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入描述:

第一行共有2个自然数N，K（6 ≤ N ≤ 40，1 ≤ K ≤ 6）

第二行是一个长度为N的数字串。

输出描述:

输出所求得的最大乘积（一个自然数）。

示例1

输入

复制

4 2

1231

输出

复制

62

思路：

定义dp状态为 dp[i][j] 代表到第i个数字，用了j个乘号，获得的最大乘积。

由于长度是40，所以肯定是会爆longlong的，用大数模板即可。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

const int MAXN=50;

struct bign

{

    int len, s[MAXN];

    bign ()

    {

        memset(s, 0, sizeof(s));

        len = 1;

    }

    bign (int num) { *this = num; }

    bign (const char *num) { *this = num; }

    bign operator = (const int num)

    {

        char s[MAXN];

        sprintf(s, "%d", num);

        *this = s;

        return *this;

    }

    bign operator = (const char *num)

    {

        for(int i = 0; num[i] == '0'; num++) ;  //去前导0

        len = strlen(num);

        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';

        return *this;

    }

    bign operator + (const bign &b) const //+

    {

        bign c;

        c.len = 0;

        for(int i = 0, g = 0; g || i < max(len, b.len); i++)

        {

            int x = g;

            if(i < len) x += s[i];

            if(i < b.len) x += b.s[i];

            c.s[c.len++] = x % 10;

            g = x / 10;

        }

        return c;

    }

    bign operator += (const bign &b)

    {

        *this = *this + b;

        return *this;

    }

    void clean()

    {

        while(len > 1 && !s[len-1]) len--;

    }

    bign operator * (const bign &b) //*

    {

        bign c;

        c.len = len + b.len;

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

        {

            for(int j = 0; j < b.len; j++)

            {

                c.s[i+j] += s[i] * b.s[j];

            }

        }

        for(int i = 0; i < c.len; i++)

        {

            c.s[i+1] += c.s[i]/10;

            c.s[i] %= 10;

        }

        c.clean();

        return c;

    }

    bign operator *= (const bign &b)

    {

        *this = *this * b;

        return *this;

    }

    bign operator - (const bign &b)

    {

        bign c;

        c.len = 0;

        for(int i = 0, g = 0; i < len; i++)

        {

            int x = s[i] - g;

            if(i < b.len) x -= b.s[i];

            if(x >= 0) g = 0;

            else

            {

                g = 1;

                x += 10;

            }

            c.s[c.len++] = x;

        }

        c.clean();

        return c;

    }

    bign operator -= (const bign &b)

    {

        *this = *this - b;

        return *this;

    }

    bign operator / (const bign &b)

    {

        bign c, f = 0;

        for(int i = len-1; i >= 0; i--)

        {

            f = f*10;

            f.s[0] = s[i];

            while(f >= b)

            {

                f -= b;

                c.s[i]++;

            }

        }

        c.len = len;

        c.clean();

        return c;

    }

    bign operator /= (const bign &b)

    {

        *this  = *this / b;

        return *this;

    }

    bign operator % (const bign &b)

    {

        bign r = *this / b;

        r = *this - r*b;

        return r;

    }

    bign operator %= (const bign &b)

    {

        *this = *this % b;

        return *this;

    }

    bool operator < (const bign &b)

    {

        if(len != b.len) return len < b.len;

        for(int i = len-1; i >= 0; i--)

        {

            if(s[i] != b.s[i]) return s[i] < b.s[i];

        }

        return false;

    }

    bool operator > (const bign &b)

    {

        if(len != b.len) return len > b.len;

        for(int i = len-1; i >= 0; i--)

        {

            if(s[i] != b.s[i]) return s[i] > b.s[i];

        }

        return false;

    }

    bool operator == (const bign &b)

    {

        return !(*this > b) && !(*this < b);

    }

    bool operator != (const bign &b)

    {

        return !(*this == b);

    }

    bool operator <= (const bign &b)

    {

        return *this < b || *this == b;

    }

    bool operator >= (const bign &b)

    {

        return *this > b || *this == b;

    }

    string str() const

    {

        string res = "";

        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;

        return res;

    }

};

istream& operator >> (istream &in, bign &x)

{

    string s;

    in >> s;

    x = s.c_str();

    return in;

}

ostream& operator << (ostream &out, const bign &x)

{

    if (x.str()=="") out<<0;

    else out << x.str();

    return out;

}

string a;

int n,k;

bign dp[41][7];

bign temp;

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    gbtb;

    cin>>n>>k>>a;

    a="0"+a;

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

    {

        for(int j=0;j<=k;j++)

        {

            dp[i][j]=0;

        }

    }

    for(int i=0;i<=k;++i)

    {

        dp[0][i]=1;

    }

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

    {

        dp[i][0]=bign(a.substr(1,i).c_str());

        for(int j=1;j<=k;j++)

        {

            for(int z=0;z<=i;z++)

            {

                temp=dp[z][j-1]*bign(a.substr(z+1,(i-z)).c_str());

                if(temp>dp[i][j])

                    dp[i][j]=temp;

            }

        }

    }

    cout<<dp[n][k]<<endl;

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

牛客假日团队赛10 L 乘积最大（dp，大数）

最新文章

热门文章

巴特西

牛客假日团队赛10 L 乘积最大 （dp，大数）

最新文章

热门文章

牛客假日团队赛10 L 乘积最大（dp，大数）