题目链接

NYOJ好像没了，不知道哪里能测评

题目及大佬题解链接

https://www.cnblogs.com/mooncode/p/10989408.html

解题思路

代码1：
dp[i][j]表示前i位数，由j个乘号得到的最大值
转移方程： dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i] j<=k<i
代码2：
dp[i][j][k]表示i到j位数由k个乘号得到的最大值
转移方程： dp[i][j][k]=max(dp[i][j][k],dp[i][t][k-1]*a[t+1][j]

未必AC的代码1

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=20;
int T,n,m;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        int a[N][N],dp[N][N],num=0,tmp=n,cnt=0;
        while(tmp){
            cnt++;
            tmp/=10;
        }

        for(int i=1;i<=cnt;i++)
            for(int j=i;j<=cnt;j++)
                a[i][j]=n%((int)(pow(10,cnt-i+1)))/(pow(10,cnt-j));

        for(int i=1;i<=cnt;i++) dp[i][0]=a[1][i];

        for(int i=2;i<=cnt;i++)
            for(int j=0;j<i && j<m;j++)
                for(int k=j;k<i;k++)
                    dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i]);

        cout<<dp[cnt][m-1]<<endl;
    }
}

未必AC的代码2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=20;
int T,n,m;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        int a[N][N],dp[N][N][N],num=0,tmp=n,cnt=0;
        while(tmp){
            cnt++;
            tmp/=10;
        }

        for(int i=1;i<=cnt;i++)
            for(int j=i;j<=cnt;j++)
                a[i][j]=n%((int)(pow(10,cnt-i+1)))/(pow(10,cnt-j)),dp[i][j][0]=a[i][j];

        for(int len=2;len<=cnt;len++)
            for(int i=1;i+len-1<=len;i++){
                int j=i+len-1;
                for(int k=1;k<len && k<m;k++)
                    for(int t=i;t<j;t++)
                        dp[i][j][k]=max(dp[i][j][k],dp[i][t][k-1]*a[t+1][j]);
            }        
        cout<<dp[1][cnt][m-1]<<endl;
    }
}