[NOIP 2000 提高组] 乘积最大 60分,对了必关

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=45;
const int M=10;
LL dp[N][M];
LL a[N][N];
LL g(int i,int j,string &s){
    LL res=0;
    for(int k=i;k<=j;++k){
        res=res*10+(s[k-1]-'0');
    }
    return res;
}
int main(){
    int n,k;
    string s;
    cin>>n>>k>>s;
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            a[i][j]=g(i,j,s);
        }
    }
    for(int i=1;i<=n;++i){
        dp[i][0]=a[1][i];
    }
    for(int i=2;i<=n;++i){
        for(int j=1;j<=k;++j){
            for(int p=j;p<i;++p){
                dp[i][j]=max(dp[i][j],dp[p][j-1]*a[p+1][i]);
            }
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}