洛谷 P1388 算式
题目描述
给出 \(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 \leq N \leq 15, 0 \leq K \leq N-1)\). 第二行为 \(N\) 个用空格隔开的数字 (每个数字在 0 到 9 之间).
输出格式:
输出文件仅一行包含一个整数, 表示要求的最大的结果
最后的结果 $ \leq maxlongint$
思路
蒟蒻我认为这一题很难
这题普遍有两种思路
第一种是 dp 第 \(i\) 个点前面有 \(j\) 个 \(*\) 号的时候最大的值是多少
这个状态可以由含有 \(q\) 个 \(*\) 的区间 A 和含有 \(j-q-1\) 个 \(*\) 的区间 B 相乘得到, 或者由含有 \(j\) 个 \(*\) 的区间 A 和含有 0 个 \(*\) 的区间 B 相加得到.
也就是 \[f_{i,j}= \max{\{ \max_{k=j}^{i-1}{\{f_{k,j-1} * \sum_{q=k+1}^{i}{a_{q}}\}}, \max_{k=j+1}^{i-1}{\{f_{k,j} + \sum_{q=k+1}^{i}{a_{q}}\}}\}}\]
代码如下
- 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]));
- if(k>=j+1) f[i][j]=max(f[i][j],f[k][j]+sum[i]-sum[k]);
- }
- }
- }
- //sum 是前缀和
但是这样的代码在洛谷上提交只能得 81 分, o(╥﹏╥)o
可以发现如下数据可以卡掉这个程序:
5 2
0 0 1 0 0
为了处理这种情况, 我发现可以有一种贪心, 遇到连续的 0 的时候就默认把一个 \(*\) 插到两个 0 中间, 就像这样:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- #define MAXN 51
- typedef long long int lli;
- lli f[MAXN][MAXN];
- int nums[MAXN],sum[MAXN];
- int i,j,k,m,n,r,t;
- bool flag;
- int main(){
- scanf("%d%d",&n,&m);
- flag=false;
- for(i=1;i<=n;i++) {
- scanf("%d",nums+i);
- if(nums[i]==0){
- if(!flag){
- flag=true;
- }else{
- i--;
- n--;
- m--;
- }
- }else{
- flag=false;
- }
- }
- sum[0]=0;
- for(i=1;i<=n;i++) sum[i]=sum[i-1]+nums[i];
- for(i=1;i<=n;i++) f[i][0]=sum[i];
- for(j=1;j<=m;j++){
- for(i=j+1;i<=n;i++){
- for(k=1;k<i;k++){
- f[i][j]=max(f[i][j],f[k][j-1]*(sum[i]-sum[k]));
- if(k>=j+1) f[i][j]=max(f[i][j],f[k][j]+sum[i]-sum[k]);
- }
- }
- }
- printf("%lld\n",f[n][m]);
- return 0;
- }
可是很遗憾, 我们提交这一份代码, 会发现还是被卡掉了一个点, 我并不知道是什么数据卡掉了这一个点, 但他确实被卡掉了. 有人通过用特判的方式 AC 了这道题, 但我不是很赞同这种做法, 因为当你仔细想一想的时候, 你会发现__还有第二种做法__
现在说第二种做法, 就是可以正常 AC 这道题的做法
观察这道题目, 你会发现这题有一点区间 dp 的意思, 因为加括号并用乘法合并正好符合区间 dp 的性质, 只是有一点限制, 那就是区间的个数有限
怎么办? 我们观察到这题的数据规模很小, 那不妨再个 dp 的数组再加一个维度, 变成这样:
\(f_{i,j,p}\) 表示区间 \([i,j]\) 中分成 \(p\) 个块时, 区间 \([i,j]\) 在合并后的最大值!
转移方程如下:
\[f_{i,j,p} = \max_{k=i}^{j-1}{\{\{\max_{q=max{\{p-(j-k),0\}}}^{\min{\{k-i,p\}}}{f_{i,k,q}*f_{k+1,j,p-q-1}} \},\{\max_{max{\{p-(j-k)+1,0\}}}^{\min{\{k-i,p\}}}{f_{i,k,q}+f_{k+1,j,p-q}}\}\}}\]
PS: 公式可能会有错, 如果有错以下方代码为准
看公式不容易理解, 代码比较直观
- for(p=1;p<=m;p++) // 枚举区间内的括号块的个数
- for(r=p+1;r<=n;r++) // 枚举区间的宽度
- for(i=1;i+r-1<=n;i++){ // 枚举左端点
- j=i+r-1; // 求出右端点
- for(k=i;k<j;k++) // 枚举区间 dp 中间点
- for(q=0;q<k-i+1&&q<p&&p-q-1<j-k;q++){
- // 枚举左侧区间中括号块的个数
- f[i][j][p]=max(f[i][j][p],f[i][k][q]*f[k+1][j][p-q-1]);
- if(p-q<j-k) f[i][j][p]=max(f[i][j][p],f[i][k][q]+f[k+1][j][p-q]);
- }
- }
最后是整个的代码
- CODE
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- #define MAXN 51
- typedef long long int lli;
- lli f[MAXN][MAXN][MAXN];
- int nums[MAXN],sum[MAXN];
- int i,j,k,m,n,r,t,p,q;
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("bigexp.in","r",stdin);
- freopen("bigexp.out","w",stdout);
- #endif
- scanf("%d%d",&n,&m);
- for(i=1;i<=n;i++) {
- scanf("%d",nums+i);
- }
- sum[0]=0;
- for(i=1;i<=n;i++) sum[i]=sum[i-1]+nums[i];
- for(i=1;i<=n;i++)
- for(j=i;j<=n;j++) f[i][j][0]=sum[j]-sum[i-1];
- for(p=1;p<=m;p++){
- for(r=p+1;r<=n;r++){
- for(i=1;i+r-1<=n;i++){
- j=i+r-1;
- for(k=i;k<j;k++){
- for(q=0;q<k-i+1&&q<p&&p-q-1<j-k;q++){
- f[i][j][p]=max(f[i][j][p],f[i][k][q]*f[k+1][j][p-q-1]);
- if(p-q<j-k) f[i][j][p]=max(f[i][j][p],f[i][k][q]+f[k+1][j][p-q]);
- }
- }
- }
- }
- }
- printf("%lld\n",f[1][n][m]);
- return 0;
- }
- # 洛谷 P1388 算式
来源: http://www.bubuko.com/infodetail-2877785.html