问题描述
题目很简单, 给出 N 个数字, 不改变它们的相对位置, 在中间加入 K 个乘号和 N-K-1 个加号,(括号随便加)使最终结果尽量大. 因为乘号和加号一共就是 N-1 个了, 所以恰好每两个相邻数字之间都有一个符号. 例如:
N=5,K=2,5 个数字分别为 1,2,3,4,5, 可以加成:
- 1*2*(3+4+5)=24
- 1*(2+3)*(4+5)=45
- (1*2+3)*(4+5)=45
- ......
输入格式
输入文件共有二行, 第一行为两个有空格隔开的整数, 表示 N 和 K, 其中(2<=N<=15, 0<=K<=N-1). 第二行为 N 个用空格隔开的数字(每个数字在 0 到 9 之间).
输出格式
输出文件仅一行包含一个整数, 表示要求的最大的结果
样例输入
5 2
1 2 3 4 5
样例输出
120
样例说明
(1+2+3)*4*5=120
参考于 https://www.cnblogs.com/cao-lei/p/6690827.html 和 https://blog.csdn.net/Tesla_meng/article/details/88614520
因为不能改变数字的相对位置, 所以只考虑乘号在哪里, 不考虑括号.
利用前缀和思想, 用 sum[i]保留前 i 个数的和便于快速求出 a[p]+a[p+1]+...+a[i]的值 (见下图), 用 dp[i][j] 保留前 i 个数中含有 j 个乘号的最大的结果. 那么我们最终要求的是 dp[n][k]. 显然, dp[i][0]=sum[i], 因为没有一个乘号, 全为加号, 所以就相当于求前 n 项和.
记 a[1]=1,a[2]=2,...,a[5]=5
dp[2][1] = dp[1][0] * a[2]. 注释: 两个数一个乘号, 即为 1*2
dp[3][1] = max(dp[2][0]a[3], dp[1][0](a[2]+a[3])). 注释: 三个数一个乘号, 即为 (1+2)*3 和 1*(2+3) 中的最大值
dp[4][1] = max(dp[3][0]a[4], dp[2][0](a[3]+a[4]), dp[1][0](a[2]+a[3]+a[4])). 注释: 四个数一个乘号, 即为 (1+2+3)*4 和(1+2)*(3+4) 和 1*(2+3+4)中的最大值
所以, 我们得到 dp[i][j] = max(dp[i][j], dp[p-1][j-1](sum[i]-sum[p-1])) (p 表示插入的乘号的位置, 2<=p<=i)
sum[i]-sum[p-1]为前缀和算法
注意数据范围, 最大的结果是 15 个 9 相乘, 9^15 超过了 int 范围, 开 long long.
- #include <bits/stdc++.h>
- using namespace std;
- long long dp[20][20];
- long long sum[20];
- int main() {
- int n, k;
- cin>> n>> k;
- for(int i = 1; i <= n; i++) {
- int t;
- cin>> t;
- sum[i] = sum[i - 1] + t;
- dp[i][0] = sum[i];
- }
- for(int i = 2; i <= n; i++) { // 数字个数逐渐增加
- for(int j = 1; j <= i - 1 && j <= k; j++) { // 乘号个数逐渐增加
- for(int p = 2; p <= i; p++) { // 乘号的位置逐渐往后移
- dp[i][j] = max(dp[i][j], dp[p - 1][j - 1] * (sum[i] - sum[p - 1]));
- }
- }
- }
- cout << dp[n][k] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3484036.html