906 AlvinZH的奇幻猜想----整数乘积

思路

难题。动态规划。

将数字串按字符串输入，处理起来更方便些。

dp[i][j]：表示str[0~i]中插入j个乘号时的乘积最大值。状态转移方程为：dp[i][j] = max(dp[i][j], dp[i-k][j-1]*convert(i-k+1,i))，k∈[1,i-j+1]，convert为数字转换函数。具体见参考代码一。

思想相同，另一份代码可能也比较好理解，见参考代码二。请思考各重循环的含义。

注意：本题要在long long范围内计算。

参考代码一

//

// Created by AlvinZH on 2017/10/30.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <cstdio>

#include <cstring>

typedef long long LL;

long long dp[22][12];

char num[22];

LL convert(int l, int r)

{

    LL res = 0;

    for (int i = l; i <= r; ++i)

        res = res*10 + (num[i]-'0');

    return res;

}

int main()

{

    //freopen("in1.txt", "r", stdin);

    //freopen("outme.txt", "w", stdout);

    int n;

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

    {

        memset(dp, 0, sizeof(dp));

        scanf("%s", num);

        int len = strlen(num);

        dp[0][0] = num[0] - '0';

        for (int i = 1; i < len; ++i)//初始化

            dp[i][0] = dp[i-1][0] * 10 + (num[i] - '0');

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

        {

            for (int j = 1; j <= (n<i? n:i); ++j)//最多有(n<i? n:i)个乘号

            {

                for (int k = 1; k <= (i-j+1); ++k)//在i-k位置后添加一个乘号

                {

                    LL tem = dp[i-k][j-1]*convert(i-k+1,i);

                    if(dp[i][j] < tem) dp[i][j] = tem;

                }

            }

        }

        printf("%lld\n", dp[len-1][n]);

    }

}

参考代码二

/*

 Author: 林未(12742)

 Result: AC    Submission_id: 417895

 Created at: Sat Nov 18 2017 16:26:54 GMT+0800 (CST)

 Problem: 906    Time: 0    Memory: 2740

*/

#include <bits/stdc++.h>

using namespace std;

long long dp[20][12];

int main()

{

    int n;

    string numstr;

    while(cin>>n>>numstr){

        memset(dp, 0, sizeof(dp));

        int len = numstr.length();

        dp[1][0]=numstr[0]-'0';

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

                dp[i+1][0]=(numstr[i]-'0')+dp[i][0]*10;

        }

        int d, u;

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

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

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

                    for(d=0, u=k+1; u<=j; u++){

                        d=d*10+(numstr[u-1]-'0');

                    }

                    if(dp[j][i]<dp[k][i-1]*d){

                        dp[j][i]=dp[k][i-1]*d;

                    }

                }

            }

        }

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

    }

    return 0;

}