914 AlvinZH的奇幻猜想----整数乘积puls

思路

难题。动态规划。

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

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根本处理不了。

方法：大数乘法。定义大数结构体，用数组存下每一位数字，做乘法时一位一位处理。建议百度学习一下大数的加减乘除，这是常见的一个面试题。具体见参考代码一。

当然，你要是会java的话，直接用BigInteger也行，简单，时间会大了点，不影响过题。具体见参考代码二。

参考代码一

//

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

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

//

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

struct BigNum {

    int len;

    int num[100];

};

int n, kk;

char s[105];//数字串

int A[105];//原数字

BigNum dp[105][12];//dp[i][j]表示前i个数字有j个乘号时的最大值。

BigNum cal(BigNum x, int l, int r)

{

    BigNum ans, y;

    memset(ans.num, 0, sizeof(ans.num));

    memset(y.num, 0, sizeof(y.num));

    y.len = r - l + 1;

    for (int i = r; i >= l; --i)

        y.num[r-i+1] = A[i];

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

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

            ans.num[i+j-1] += x.num[i] * y.num[j];

        }

    }

    int newLen = x.len + y.len -1;

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

        ans.num[i+1] += ans.num[i]/10;

        ans.num[i] = ans.num[i]%10;

    }

    if(ans.num[newLen+1] > 0) newLen++;

    ans.len = newLen;

    /*for (int i = ans.len; i >= 1; --i)

        printf("%d", ans.num[i]);

    printf("\n");*/

    return ans;

}

BigNum cmp(BigNum x, BigNum y)//比较大小

{

    if(x.len > y.len) return x;

    else if(x.len < y.len) return y;

    for (int i = x.len; i >=1 ; --i) {

        if(x.num[i] > y.num[i]) return x;

        else if(x.num[i] < y.num[i]) return y;

    }

    return x;

}

int main()

{

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

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

    while(~scanf("%d %s", &kk, s))

    {

        for (int i = 0; i < 105; ++i) {

            for (int j = 0; j < 12; ++j) {

                dp[i][j].len = 0;

                memset(dp[i][j].num, 0, sizeof(dp[i][j]));

            }

        }

        n = strlen(s);

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

            A[i] = s[i-1] - '0';

        //初始化没有添加乘号的情况

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

            for (int j = i; j >= 1; --j) {

                dp[i][0].num[++dp[i][0].len] = A[j];

            }

        }

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

            for (int k = 1; k <= min(kk, i-1); ++k) {

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

                    dp[i][k] = cmp(dp[i][k], cal(dp[j][k-1], j+1, i));

                }

            }

        }

        for (int i = dp[n][kk].len; i >= 1; --i) {

            printf("%d", dp[n][kk].num[i]);

            if(dp[n][kk].num[dp[n][kk].len] == 0) break;

        }

        printf("\n");

    }

}

参考代码二

/*

 Author: 赵立晨(12657)

 Result: AC    Submission_id: 402925

 Created at: Sun Nov 12 2017 13:24:46 GMT+0800 (CST)

 Problem: 914    Time: 451    Memory: 48880

*/

//package main;

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

    public static void main(String args[]){

        BigInteger dp[][]=new BigInteger[107][17];

        BigInteger num[][]=new BigInteger[107][107];

        Scanner in=new Scanner(System.in);

        while (in.hasNext()){

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

                for (int j=0;j<=10;j++) dp[i][j]=BigInteger.ZERO;

            int n=in.nextInt();

            String a=in.next();

            for (int i=0;i<a.length();i++){

                for (int j=i;j<a.length();j++){

                    num[i][j]=new BigInteger(a.substring(i,j+1));

                }

            }

            dp[0][0]=BigInteger.ZERO;

            for (int i=0;i<a.length();i++) dp[i][0]=num[0][i];

            for (int i=0;i<a.length();i++){

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

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

                        dp[i][k]=dp[i][k].max(dp[j-1][k-1].multiply(num[j][i]));

                    }

                }

            }

            System.out.println(dp[a.length()-1][n]);

        }

        in.close();

    }

}