如何把一个正整数 $N$（$N$长度 $<$ $20$）划分为$M$（$M$ $>$ $1$）个部分，使这$M$个部分的乘积最大。$N$、$M$从键盘输入，输出最大值及一种划分方式。

输入数据：

第一行一个正整数$T$($T$ $<=$ $10000$)，表示有$T$组数据。

接下来$T$行每行两个正整数$N$，$M$。

输出数据：

对于每组数据

第一行输出最大值。

第二行输出划分方案，将$N$按顺序分成$M$个数输出，两个数之间用空格格开。

样例

输入文件：$separate.in$

1
199 2

输出文件：$separate.out$

171
19 9

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#define int long long

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

inline int read(){
    char ch=getchar();
    int x=0,w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}


int T,m,len;
string s;
int a[3005][3005],f[3005][3005],path[3005][3005];//a[i][j]:i->j的数    f[i][j]:前i位划分j次
void work(){
    len=s.size();
    for(int i=0;i<len;i++){
        int sum=0;
        for(int j=i;j<len;j++){
            sum=sum*10+s[j]-'0';
            a[i+1][j+1]=sum;
        }
    }
    for(int i=1;i<=len;i++) f[i][0]=a[1][i];
}
void print(int length,int num){
    if(!num) return;
    print(path[length][num],num-1);
    for(int i=path[length][num]+1;i<=length;i++) cout<<s[i];
    cout<<" ";
}


signed main() {
    T=read();
    while(T--){
        cin>>s;
        m=read();
        work();
        //for(int i=1;i<=len;i++) cout<<a[1][i]<<" ";
        for(int i=2;i<=len;i++)
            for(int j=1;j<=m&&j<i;j++)
                for(int k=1;k<i;k++){
                    //f[i][j]=max(f[i][j],f[k][j-1]*a[k+1][i]);
                    if(f[k][j-1]*a[k+1][i]>f[i][j]){
                        f[i][j]=f[k][j-1]*a[k+1][i];
                        path[i][j]=k;
                    }
        }
        //for(int i=0;i<=m;i++) cout<<f[len][i]<<" ";
        cout<<f[len][m-1]<<"\n";
        //for(int i=0;i<=m;i++) cout<<path[len][i]<<" ";
        print(len,m);
    }
    return 0;
}

求助如何输出方案