问题描述
题目很简单，给出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
#include <stdio.h> #include <stdlib.h> #define min(a, b) a > b ? b : a #define max(a, b) a > b ? a : b long long dp[16][16] = {0}; //dp[i][j]表示前i个数中有j个乘号时，所得最大值 int sum[16] = {0}; //sum[i]表示前i个数之和 int main() { int N, K, i = 1, j, k, t; scanf("%d %d", &N, &K); int num[16]; for (; i <= N; i++) { scanf("%d", &num[i]); sum[i] = sum[i - 1] + num[i]; } //如果没有乘号的情况/连加情况 for (i = 1; i <= N; i++) { dp[i][0] = sum[i]; } //dp for (i = 2; i <= N; i++) { for (j = 1; j <=i-1; j++)//最大有i-1个*号 { for (k = 2; k <= i; k++) //k为这个乘号的位置（第k个数） { dp[i][j] = max(dp[i][j], dp[k - 1][j - 1] * (sum[i] - sum[k - 1])); //求前i个数有j个乘号的情况中最大的情况 //第k个数前的最优情况*k到i个数的和， } } } printf("%lld\n", dp[N][K]); return 0; }
