题意：给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
分析：根据区间dp的思想，我们定义dp [ i ] [ j ]为从开始到 i 中加入 j 个乘号得到的最大值。

那么我们可以依次计算加入1—-m-1个乘号的结果

而每次放入x个乘号的最大值只需枚举第x个乘号的放的位置即可

dp[i][j]=MAX(dp[i][j],dp[k][j−1]∗a[k+1][i])

代码如下:

//
//Created by BLUEBUFF 2016/1/10
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 210;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head

char s[30];
int m;
LL a[30][30], dp[30][30];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s%d", s, &m);
        int len = strlen(s);
        CLR(a, 0);
        CLR(dp, 0);
        for(int i = 0; i < len; i++){
            a[i][i] = s[i] - '0';
            for(int j = i + 1; j < len; j++){
                a[i][j] = a[i][j - 1] * 10 + (s[j] - '0');
            }
        }
        for(int i = 0; i < len; i++) dp[i][0] = a[0][i];
        for(int j = 1; j < m; j++){
            for(int i = j; i < len; i++){
                for(int k = 0; k < i; k++){
                    dp[i][j] = max(dp[i][j], dp[k][j - 1] * a[k + 1][i]);
                }
            }
        }
        cout << dp[len - 1][m - 1] << endl;
    }
    return 0;
}