Luogu 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<=N<=15, 0<=K<=N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出格式

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

最后的结果<=maxlongint

输入输出样例

输入样例#1：

1 2	5 2 1 2 3 4 5

输出样例#1：

如果可以改变顺序，一个最大堆就解决了。

奈何不能改变相对顺序，于是采用dp。

用ans[i][j]表示在前i个数的序列中插入j个乘号的最优解。由于乘号和加号数量之和为n-1，所以当乘号数量确定后，加号数量也唯一确定。

之后可以发现，因为不能改变顺序，所以在前i个数中插入乘号后，剩下的连续序列必然相加。故有状态转移方程：

1	ans[i][j]=max(ans[i][j],ans[t][j-1]*(a[i]-a[t]))

其中t表示前i个数中某个小于i的位置，ans[t][j-1]表示在前i个数构成的序列中的一段由前t个数构成的子序列里插入j-1个乘号的最优解。

附代码

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n,k,a[20],ans[20][20]={0};
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i-1) a[i]+=a[i-1];
        ans[i][0]=a[i];
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=min(k,i-1);j++)
            for(int t=j;t<i;t++)
                ans[i][j]=max(ans[i][j],ans[t][j-1]*(a[i]-a[t]));
    cout<<ans[n][k];
    return 0;
}