♉ CSP_S 组真题
2000年
2. 乘积最大

线上OJ:

一本通:1821:【00NOIP提高组】乘积最大 (opens in a new tab)
AcWing:1026. 乘积最大 (opens in a new tab)
洛谷:P1018 [NOIP2000 提高组] 乘积最大 (opens in a new tab)

核心思想:

样例图

1、从上图中可以推出:前i个数 插入j个符号的最大值 = 前k个数(k < i)插入j-1个符号的最大值 * 从第 K+1 ~ 第i个位置组成的数字。即:
dp[i][j]=max(dp(i,j),dp[k][j1]a[k+1][i])dp[i][j] = max(dp(i, j), dp[k][j-1] * a[k+1][i] )

2、先计算a[i][j],即表示字符串第i~第j个位置组成的数是多少

举例: 16872的 a[1][3]为168,a[2][4]为687。在dp方程中用得到。
备注 :
在计算 a[i][j]a[i][j] 时,a[i][j]=a[i][j1]10+(c[j1]0)a[i][j] = a[i][j - 1] * 10 + (c[j - 1] - '0'); c[j-1] 为输入的第 j 个字符(从c[0]开始)

题解代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int n, t;
ll a[50][50];  // a[i][j] 表示字符串第i~第j个位置组成的数是多少。举例: 16872的 a[1][3]为168,a[2][4]为687 
ll dp[50][7];  // (6<=N<=40,1<=K<=6)  dp[i][j]表示前i个数插入j个符号的最大值 
char c[50];  // c[i]读入的第i个字符 
 
/*
前i个数插入j个符号的最大值 = 前k个数(k<i)插入j-1个符号的最大值 * 从第 K+1 ~ 第i个位置组成的数字 
dp[i][j] = max(dp(i,j), dp[k][j-1] * a[k+1][i] ) 
*/ 
int main()
{
    // 读入 	
	cin >> n >> t;
	for(int i = 0; i < n; i++)  cin >> c[i];
 
	// 初始化 
	for(int i = 1; i <= n; i++) 
        for(int j = i; j <= n; j++)  
			a[i][j] = a[i][j - 1] * 10 + (c[j - 1] - '0'); 
    
	for(int i = 1; i <= n; i++) 
		dp[i][0] = a[1][i];  // 前i个数插入0个乘号时,就是前i个位置组成的数字本身 
	
	// dp
	for(int i = 1; i <= n; i++)  // 穷举前i个数,i不超过n 
		for(int j = 1; j <= t; j++)   // 插入j个乘号,不超过t 
			for(int k = 1; k < i; k++)    // 穷举前k个数,不超过i-1 
				dp[i][j] = max(dp[i][j], dp[k][j-1] * a[k+1][i]);
	
	printf("%lld", dp[n][t]);
	return 0;
}