乘积最大

发表于 更新于 分类于

Problem’s Website

  • 乘积最大

    Solution

  • 首先这道题要dp求解，其次根据数据范围，在计算过程中要用高精。

  • dp：我们设f[i][j]表示第i个数后放第j个乘号的最大值，dp[i]表示最最后一个乘号放在第i位数的最大值。我们首先枚举i，f[i][1]可以直接计算，再从2到k枚举j,枚举i之前的数，进行转移，方程为

    1
    2
    3
    if(f[rei][j - 1].vis) {
    	f[i][j] = Max(f[i][j], GJ(f[rei][j - 1], calc(rei + 1, i));
    }

    dp[i]在之后转移，方程为

    1
    2
    if(f[i][j].vis)
    	dp[i] = GJ(f[i][j], calc(i + 1, n));

  • 高精，具体说是高精乘，本人表示不想解释，因为自己都快忘了。。。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct node {
    	bool vis;
    	int bit;
    	int num[50];
    }f[50][10], dp[50];
    int n, k;
    char s[50];
    int a[50];
    node calc(int l, int r) {
    	node aa;
    	aa.bit = r - l + 1;
    	aa.vis = true;
    	for(int i = 1; i <= aa.bit; i++)
    		aa.num[i] = a[r - i + 1];
    	return aa;
    }
    node Max(node a, node b) {
    	if(!a.vis || a.bit < b.bit) return b;
    	if(!b.vis || a.bit > b.bit) return a;
    	for(int i = a.bit; i >= 1; i--)
    		if(a.num[i] > b.num[i]) return a;
    		else if(a.num[i] < b.num[i]) return b;
    }
    node GJ(node a, node b) {
    	node aa;
    	aa.vis = true;
    	aa.bit = a.bit + b.bit - 1;
    	for(int i = 1; i <= aa.bit; i++)
    		aa.num[i] = 0;
    	for(int i = 1; i <= a.bit; i++)
    		for(int j = 1; j <= b.bit; j++)
    			aa.num[i + j - 1] += a.num[i] * b.num[j];
    	int mod = 0;
    	for(int i = 1; i <= aa.bit; i++) {
    		aa.num[i] += mod;
    		mod = aa.num[i] / 10;
    		aa.num[i] %= 10;
    	}
    	while(mod > 0) {
    		aa.num[++aa.bit] = mod % 10;
    		mod /= 10;
    	}
    	return aa;
    }
    int main() {
    	scanf("%d%d", &n, &k);
    	scanf("%s", s + 1);
    	for(int i = 1; i <= strlen(s + 1); i++)
    		a[i] = s[i] - '0';
    	for(int i = 1; i <= n; i++) {
    		dp[i].vis = false;
    		for(int j = 1; j <= k; j++)
    			f[i][j].vis = false;
    	}
    	for(int i = 1; i <= n - 1; i++) {
    		f[i][1] = calc(1, i);
    		for(int j = 2; j <= k; j++) {
    			for(int rei = j - 1; rei < i; rei++) {
    				if(f[rei][j - 1].vis)
    					f[i][j] = Max(f[i][j], GJ(f[rei][j - 1], calc(rei + 1, i)));
    			}
    		}
    		if(f[i][k].vis)
    			dp[i] = GJ(f[i][k], calc(i + 1, n));
    	}
    	node ans;
    	for(int i = 1; i <= n - 1; i++) {
    		node tmp = Max(dp[i], ans);
    		ans = tmp;
    	}
    	for(int i = ans.bit; i >= 1; i--)
    		printf("%d", ans.num[i]);
    	return 0;
    }

rp++