这题用DP或者DFS均能过。 在COJ上看了ahyangyi大神的代码，手写了个bigint的结构体，遂模仿之，果然很好使
典型的DP问题
设w(h,q)表示从h位开始的q位数字组合所成的十进制数,m(i,j)表示前i位数字串插入j个乘号所得的最大乘积,初始值为：
m(i,0) = w(0,q) ;
动规方程如下所示：
if (j==0) m(i,j) = w(0,i) ;
else if(j>0)
m(i,j) = max { m(d,j-1)*w(d+1,i-d) } ps: 其中 0<= d < i
下标均从0开始
DP版本
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 100005
#define eps 1e-10
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct BigInteger
{int len;int d[105];BigInteger(){len = 1; d[0] = 0;}BigInteger(string s){len = s.length();reverse(s.begin(), s.end());for(int i = 0; i < len; i++)d[i] = s[i] - '0';while(len > 0 && d[len - 1] == 0) len--;if(!len) d[len++] = 0;}void operator *=(const BigInteger &a){int tmp[105];for(int i = 0; i < len + a.len; i++) tmp[i] = 0;for(int i = 0; i < len; i++)for(int j = 0; j < a.len; j++)tmp[i + j] += d[i] * a.d[j];len = len + a.len - 1;for(int i = 0; i < len; i++){tmp[i + 1] += tmp[i] / 10;tmp[i] %= 10;}if(tmp[len]) len++;for(int i = 0; i < len; i++) d[i] = tmp[i];while(len > 0 && d[len - 1] == 0) len--;if(!len) d[len++] = 0;}bool operator <(const BigInteger &a)const{if(len != a.len) return len < a.len;for(int i = len - 1; i >= 0; i--)if(d[i] != a.d[i]) return d[i] < a.d[i];return false;}void out(){for(int i = len - 1; i >= 0; i--)printf("%d", d[i]);printf("\n");}
}dp[55][11];
int n, m;
char s[105];
int main()
{scanf("%d%d%s", &n, &m, s);string tx = s;for(int i = 0; i < n; i++){dp[i][0] = BigInteger(tx.substr(0, i + 1));for(int j = 1; j <= m; j++){for(int k = 0; k < i; k++){BigInteger q(tx.substr(k + 1, i - k));q *= dp[k][j - 1];if(dp[i][j] < q) dp[i][j] = q;}}}dp[n - 1][m].out();return 0;
}
DFS版本
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 100005
#define eps 1e-10
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct BigInteger
{int len;int d[105];BigInteger(){len = 1; memset(d, 0, sizeof(d)); d[0] = 1;}BigInteger(string s){len = s.length();for(int i = 0; i < len; i++)d[i] = s[i] - '0';while(len > 0 && d[len - 1] == 0) len--;if(!len) d[len++] = 0;}void operator *=(const BigInteger &a){int tmp[105];for(int i = 0; i < len + a.len; i++) tmp[i] = 0;for(int i = 0; i < len; i++)for(int j = 0; j < a.len; j++)tmp[i + j] += d[i] * a.d[j];len = len + a.len - 1;for(int i = 0; i < len; i++){tmp[i + 1] += tmp[i] / 10;tmp[i] %= 10;}if(tmp[len]) len++;for(int i = 0; i < len; i++) d[i] = tmp[i];while(len > 0 && d[len - 1] == 0) len--;if(!len) d[len++] = 0;}bool operator <(const BigInteger &a)const{if(len != a.len) return len < a.len;for(int i = len - 1; i >= 0; i--)if(d[i] != a.d[i]) return d[i] < a.d[i];return false;}void out(){for(int i = len - 1; i >= 0; i--)printf("%d", d[i]);printf("\n");}
}ans;
int n, k;
char s[105];
void dfs(BigInteger t, int m, int x)
{if(m == 0){if(ans < t) ans = t;return;}for(int i = x ; i < n - m + 1; i++){BigInteger q = t;string fk = s;fk = fk.substr(x, i - x + 1);reverse(fk.begin(), fk.end());q *= BigInteger(fk);dfs(q, m - 1, i + 1);}
}
int main()
{scanf("%d%d%s", &n, &k, s);ans.d[0] = 0;BigInteger t;dfs(t, k + 1, 0);ans.out();return 0;
}