题目描述

今年是国际数学联盟确定的“2000――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

    设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

1） 3*12=36

2） 31*2=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入输出格式

输入格式：

程序的输入共有两行：

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）

第二行是一个长度为N的数字串。

输出格式：

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

输入输出样例

4  2
1231

62

        突然发现博客没DP题啊，然后就现水了一道占个位置。

        一道经典的DP。首先，我们确定当前状态dp[i][j]表示 放的乘号个数为i、放到了第j个数字。

        然后考虑转移方程。首先我们可以这样想，一个长度为j的序列当没有加入一个乘号时向其中加

        入一个乘号是可以用O(N) 时间枚举最优解的（只用枚举乘号位置）。那么我们是不是可以考虑

        用这种方法对于每一组K相同的状态，枚举出长度为j(j -> 1~N)的每一种最优解呢？因为我每一

        次枚举K时对于前面的dp[K-1]的一组状态已经保证为最优解了。于是我们就有了状态转移方程：

                     dp[j][i]=max{dp[k][i-1]*num[k+1][j]};（1<=i<=K ;1<=j<=N;1<=k<=j）

    其中num[a][b]表示从下标a到b的数字组成的数的大小(对于1231  num[2][4]=231)        时间复杂度O(N^2*m)        另外，一看到这道题本来应该是用高精度的，结果不知道为什么数据太水，Long Long就水过了。        对于恶心的long long 的读入，屈服于iostream黑恶势力……

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=40;
ll num[maxn][maxn]={ };
ll dp[maxn][20]={ };
int n,m;
char s[50];

void init(int n){
    memset(num,0,sizeof(num));
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        num[i][i]=1LL*(s[i-1]-'0');
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            ll id=1LL*(s[j-1]-'0');
            num[i][j]=num[i][j-1]*10+id;
        }
    }
}

int main(){
    cin>>n>>m;
    cin>>s;
    init(n);
    for(int i=1;i<=n;i++)
        dp[i][0]=num[1][i];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
            for(int k=1;k<=j;k++)
                if(dp[k][i-1]*num[k+1][j]>dp[j][i])
                    dp[j][i]=dp[k][i-1]*num[k+1][j];
    }
    cout<<dp[n][m];
    return 0;
}

----------+--------+------18/3/27------+--------+--------

洛谷数据加强了QAQ……这里挂一个大整形高精度:

#include<cstring>
#include<algorithm>
using namespace std;
namespace BIGINT {
 #define LL long long
 struct INT1024 {
     int len;
     int s[1030];
     INT1024() {clean();}
     void clean() {memset(s, 0, sizeof(s)), len = 0;}
     void operator = (int x) {
         for(; x; x /= 10) s[len++] = x % 10;
     }
     void print() {
         for(int i = len - 1; i >= 0; --i) printf("%d", s[i]);
         putchar('\n');
     }
 };
 INT1024 c;
 INT1024 operator + (INT1024 a, INT1024 b) {
     int len = max(a.len, b.len);
     c.clean();
     c.len=len;
     for(int i = 0;i < len; ++i) c.s[i] = a.s[i] + b.s[i];
     for(int i = 0;i < len; ++i) c.s[i + 1] += c.s[i] / 10, c.s[i] %= 10;
     if(c.s[len]) ++c.len;
     return c;
 }
 INT1024 operator - (INT1024 a, INT1024 b) {
     c.clean();
     for(int i = 0; i < a.len; ++i) {
         c.s[i] += a.s[i] - b.s[i];
         if(c.s[i] < 0) c.s[i] += 10, --a.s[i + 1];
     }
     int len = a.len - 1;
     for(; !c.s[len]; --len);
     c.len = len + 1;
     return c;
 }
 INT1024 operator * (INT1024 a, INT1024 b) {
     int len = a.len + b.len - 1;
     c.clean();
     c.len = len;
     for(int i = 0;i < a.len; ++i) 
 for(int j = 0; j < b.len; ++j) 
 c.s[i + j] += a.s[i] * b.s[j];
     for(int i = 0;i < len; ++i) c.s[i + 1] += c.s[i] / 10, c.s[i] %= 10;
     if(c.s[len]) ++c.len;
     return c;
 }
}
 ​