题解 P1388 【算式】

· · 题解

蒟蒻来发布一篇并没有AC的题解qwq

因为是蒟蒻，所以就讲一下自己的错误思路历程吧。

首先我做了P1103书本整理 这道水题P1103 传送门

于是看到这道题，本蒟蒻灵机一动，打算活学活用，于是便设出了

    f[i][j] 表示前i个数里面插j个乘号的最优解

动态转移方程：

f[i][j]=max(f[i][j],f[i-p][j-p]*a[i-p+1]*...*a[i](p!=0)

f[i][j]=max(f[i][j],a[i]+f[i-1][j])(p==0)

这里的p表示后面p个数之间都取乘号（即i-p+1到i之间都取乘号，包括与f[i-p][j-p]的连接）

当然可以后p个之间都取乘号，p前面的数一些取乘号

蒟蒻的温馨提示：对于这种边界的确认一定要认真用手模一下确认清楚啊qwq

于是全wa代码出现了：

#include<cstdio>
#include<algorithm>
const int N=25;
//全wa代码 
using namespace std;
int f[N][N];
int n,k,a[N];
int solve(int l,int r){
    int sum=1;
    for(int i=l;i<=r;i++){
        sum*=a[i];
    }
    return sum;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    f[1][0]=a[1];
    for(int i=2;i<=n;i++){
        f[i][0]=f[i-1][0]+a[i];
        f[i][i-1]=f[i-1][i-2]*a[i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=k&&j<=i-1;j++){
            for(int p=0;p<=j;p++){
                if(p==0) f[i][j]=max(f[i][j],a[i]+f[i-1][j]);//错误 因为不等于书，括号有优先级 
                else{
                    f[i][j]=max(f[i][j],f[i-p][j-p]*solve(i-p+1,i));
                    //printf("%d %d %d\n",i,j,f[i][j]);
                }
                printf("%d %d %d\n",i,j,f[i][j]);
            }
        }
    }
    printf("%d",f[n][k]);
    return 0;
}

发现问题出现在哪里了ma

蒟蒻，放弃了思考

当发现全wa了并且数据不能下载了之后，本蒟蒻愤怒的找了一篇看起来和这个写的蛮像的代码，发动了对拍败者食尘：

我们来看这一组数据：


6 4

3 6 9 5 8 2

输出每一组i,j,f[i][j]

当i=4,j=1的时候

全wa代码输出 95

dalao代码输出 140

蒟蒻震惊了，不相信这个事实，然后不服输地用手算了一遍，发现：

p==0 a[4]+f[3][1]=95
p!=0 a[4]*f[3][0]=95

然后令人心痛地事实出现了，蒟蒻地方程推错了。

不愧是蒟蒻！居然做出我们都不会做的事情！

问题出在当p==0的时候

a[4]+f[3][1] 即a[4]+a[3]*（a[1]+a[2]）

即（3+7）*9+5=95

然而细细思考一下，最优解应该是

（3+7）*（9+5）=140

反思总结：

人越是工于心计，就越会栽在自己预料不到的状况上

因为此题和书本摆放不同，题目中说明括号随便加，那么就可以用括号改变计算的优先级

于是我们改动方程一下

f[i][j]=max(f[i][j],f[p][j-1]*(sum[i]-sum[p]));

p表示最后一个乘号的位置

放上代码：

#include<cstdio>
#include<algorithm>
const int N=25;
using namespace std;
int f[N][N];
int n,k,a[N],sum[N];
int solve(int l,int r){
    int sum=1;
    for(int i=l;i<=r;i++){
        sum*=a[i];
    }
    return sum;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    f[1][0]=a[1];
    for(int i=2;i<=n;i++){
        f[i][0]=f[i-1][0]+a[i];
        f[i][i-1]=f[i-1][i-2]*a[i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=k&&j<=i-1;j++){
            for(int p=j;p<=i-1;p++){//最后一个乘号在哪里 
                f[i][j]=max(f[i][j],f[p][j-1]*(sum[i]-sum[p])); 
                //printf("%d %d %d\n",i,j,f[i][j]);
            }
        }
    }
    printf("%d",f[n][k]);
    return 0;
}

其实和之前dalao的思路是一样的，不过这道题搞了那么久，一定要发一篇题解来表示本蒟蒻的贫弱

祝2019 CSP-S rp++

夺走你赞的不是别人，ko no MAXI da!