「BSOJ2316」 最大的算式 - Dp

本文主要是介绍「BSOJ2316」 最大的算式 - Dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题目很简单，给出N个数字，不改变它们的相对位置，在中间加入$K$个乘号和$N-K-1$个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是$N-1$个了，所以恰好每两个相邻数字之间都有一个符号。例如：
$N=5，K=2，5$个数字分别为$1,2,3,4,5$，可以加成：
$$\begin{gathered} 1\times 2\times (3+4+5)=24 \\ 1\times (2+3)\times (4+5)=45 \\ (1\times 2+3)\times (4+5)=45 \\ \dots \end{gathered}$$

输入格式

输入文件共有两行，第一行为两个有空格隔开的整数，表示$N$和$K$，其中（$2\le N\le 15,0\le K\le N-1$）。第二行为$N$个用空格隔开的数字（每个数字在$0$到$9$之间）。

输出格式

输出文件仅一行包含一个整数，表示要求的最大的结果。

样例输入

5 2
1 2 3 4 5

样例输出

120

样例解释

$(1+2+3)\times 4\times 5=120$

分析

由于本题数据范围较弱，所以各种神仙算法都能过。

首先，看到本题，应该以下就能反应出来这是DP。其次，本题也有点像乘积最大，就试试那种方法。

定义$f[i][j]$为前$i$个数字插入$j$个乘号所取得的最大值，则很容易推导出状态转移方程：
f [ i ] [ j ] = max ⁡ j ≤ k &lt; i { f [ k ] [ j ] + s u m [ i ] − s u m [ k ] , f [ k ] [ j − 1 ] × ( s u m [ i ] − s u m [ k ] ) } f[i][j]=\max_{j\le k &lt; i} \{ f[k][j]+sum[i]-sum[k] ,f[k][j-1]\times(sum[i]-sum[k]) \} f[i][j]=j≤k<imax​{f[k][j]+sum[i]−sum[k],f[k][j−1]×(sum[i]−sum[k])}
其中，$sum[i]$表示前$i$个数字的和。

还是讲讲这个方程吧。

在第$k$个位置后可以插一个乘号，就是$f[k][j-1]\times (sun[i]-sum[k])$，而如果在第$k$个位置后不插入乘号，就为$f[k][j]+sum[i]-sum[k]$，所以在取个最大值就转移到$f[i][j]$了。

由此，代码也不难得出。

代码

本蒟蒻的代码写得有点稀奇古怪，一开始没注意循环的顺序和状态的可能性，所以写出了$5$重循环，但还是过了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <queue>
#define inf 0x7fffffff/2
using namespace std;
int n,k,a;
long long f[20][20];
long long sum[20];
int main() {scanf("%d%d",&n,&k);for (int i=1;i<=n;i++)scanf("%d",&a),sum[i]=sum[i-1]+a,f[i][0]=sum[i];for (int i=2;i<=n;i++)for (int j=1;j<=k;j++)for (int m=1;m<i;m++) {f[i][j]=max(f[i][j],f[m][j-1]*(sum[i]-sum[m]));for (int t=j;t<m;t++)for (int s=m+1;s<i;s++)
f[i][j]=max(f[i][j],f[t][j-1]+(sum[m]-sum[t])*(sum[s]-sum[m])+sum[i]-sum[s]);}printf("%lld",f[n][k]);return 0;
}

下面是某位神犇的代码。

#include<iostream>
using namespace std;
long long f[16][16],sum[16];
int main()
{int n,m,i,j,k;long long x;cin>>n>>m;for(i=1;i<=n;i++) cin>>x,sum[i]=sum[i-1]+x,f[i][0]=sum[i];for(j=1;j<=m;j++)for(i=j+1;i<=n;i++)for(k=j;k<i;k++){f[i][j]=max(f[i][j],f[k][j-1]*(sum[i]-sum[k]));f[i][j]=max(f[i][j],f[k][j]+sum[i]-sum[k]);}cout<<f[n][m];
}

这篇关于「BSOJ2316」 最大的算式 - Dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---