[oiclass] maximum formula

problem : The biggest formula

Title Description

The subject is very simple , give N A digital , Don't change their relative position , Add... In the middle K A multiplication sign and N-K-1 Plus sign ,（ Put in parentheses ） Maximize the final result . Because the multiply sign and the plus sign are N-1 A the , So there's just a sign between every two adjacent numbers . for example ：
N=5, K=2,5 The numbers are 1、2、3、4、5, Can add ：

1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
...

Input

The input file has two lines , The first line is two integers separated by spaces , Express N and K, among (2<=N<=15, 0<=K<=N-1). Second behavior N A number separated by a space （ Each number is in 0 To 9 Between ）.

Output

The output file contains only one integer on one line , Represents the maximum result required
The final result <=maxlongint

Examples

#1

Input

5 2
1 2 3 4 5

Output

120

Previous ideas

Think f[i][j][k] It should be defined like this ：
set up f[i][j][k] For in [i , j] Within the interval of k A multiple sign
State transition equation ：

f[i][j][k] =  max4(f[i+1][j][k]+a[i],f[i][j-1][k]+a[j],
				f[i+1][j][k-1]*a[i],f[i][j-1][k-1]*a[j]);

Then the wrong code should be like this ：

#include<bits/stdc++.h>
using namespace std;
const int N = 101;
int n,m,a[N],f[N][N][N*11];
int main(){
    
    cin >> n >> m; 
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=n;i>0;i--){
    
        for(int j=i;j<=n;j++){
    
            for(int k=0;k<=m;k++){
    
                f[i][j][k] = max(f[i+1][j][k]+a[i],
                             max(f[i+1][j][k-1]*a[i],
                             max(f[i][j-1][k]+a[j],
                                 f[i][j-1][k-1]*a[j])));
            }
        }
    }
    cout << f[1][n][m] << endl;
}
/************************************************************** Language: C++ Result:  Wrong answer 50 ****************************************************************/

got 50 branch , Later, I found several error examples and found them by comparison ：
This section can be cut from more than two sides , It can also be cut from any position in the middle , If you cycle the middle line , Then the number of multiplication signs can be more or less . At this time f[i][j][k] The initialization of will become -INF This is running max Function to find the optimal solution

On AC Code ：

#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
const int N = 110;
int n,m,a[N],f[N][N][N];
int main(){
    
    cin >> n >> m;
    for(int i=1;i<=n;i++){
    cin >> a[i];}
    for(int i=1;i<=n;i++){
    
        f[i][i][0] = a[i];
    }
    for(int i=n;i>0;i--){
    
        for(int j=i+1;j<=n;j++){
    
            for(int k=0;k<=min(j-i,m);k++){
    
                if(m-(n-(j-i))>=k){
    
                    f[i][j][k]=-INF;
                    continue;
                }
                for(int z=i;z<j;z++){
    
                    for(int y=0;y<=k;y++){
    
f[i][j][k] = max(f[i][j][k],f[i][z][y]+f[z+1][j][k-y]);
                        if(y==0){
    
f[i][j][k] = max(f[i][z][y]*f[z+1][j][k-y-1],
                f[i][j][k]);
                        }
                        else{
    
f[i][j][k] = max(f[i][z][y-1]*f[z+1][j][k-y],
                f[i][j][k]);
                        }
                    }
                }
            }
        }
    }
// cout << f[3][5][1] <<endl;
    cout << f[1][n][m] << endl;
}
/************************************************************** Language: C++ Result:  correct 100 Time:0 ms Memory:6912 kb ****************************************************************/