P 1018積算最大(ダイナミックプランニング+高精度)


P 1018積算最大(ダイナミックプランニング+高精度)
タイトルの説明
今年は国際数学連盟が確定した「2000――世界数学年」であり、わが国の有名な数学者華羅庚氏の生誕9090周年にもふさわしい.華羅庚さんの故郷江蘇金壇で、ユニークな数学知能コンテストの活動を組織し、あなたの親友XZXZも参加することができました.イベントでは、司会者がイベントに参加したすべての選手にこのようなテーマを出しました.
長さNNの数字列が設けられており、KK個の乗号を用いてK+1 K+1個の部分に分割することを選手に要求し、このK+1 K+1個の部分の積を最大にすることができるように分法を見つけた.
また、司会者は選手が問題の意味を正しく理解できるようにするために、次のような例を挙げた.
数字の列があります:312312、N=3、K=1 N=3、K=1の時以下の2種類の分法があります:
1、 3\times 12=363×12=362、 31\times 2=6231×2=62
このとき,タイトル要求に合致した結果は,31times 2=6231であった.×2=62
今、あなたの良い友达XZXZを助けてプログラムを設計して、正しい答えを求めてください.
にゅうしゅつりょくけいしき
入力形式:
プログラムの入力は2行あります.
第1行は22個の自然数N,KN,K(6≦N≦40,1≦K≦66≦N≦40,1≦K≦6)を有する.
2行目は長さNNの数字列です.
出力フォーマット:
結果は画面に表示され、入力に対して求めた最大積(自然数)が出力されます.
入出力サンプル
入力サンプル#1:コピー
4  2
1231

出力サンプル#1:コピー
62

説明
NOIp 2000向上グループ第二題
#include
#include
#include
using namespace std;
long long dp[45][60]; //     :dp[i][j]     i      j             
string str;           //     :
int n,k;//n    k   
long long integer[45];
long long cut(int left,int right)
{
    int i;
    long long product=0;
    long long d=1;
    for(i=right;i>=left;i--)
    {
        product+=integer[i]*d;
        d*=10;
    }
    return product;
}
int main()
{
    int i;
    int a,b;
    scanf("%d%d",&n,&k);
    cin>>str;
    for(i=1;i<=n;i++)
    integer[i]=str[i-1]-'0';
    for(i=1;i<=n;i++)
    dp[i][0]=cut(1,i);                     //     
    for(i=2;i<=n;i++)                      //      i   
    {                                      //               ,  i 2  
        for(a=1;a<=min(i-1,k);a++)          //       
        {                                  //             ,         ,           ,  i 1  。0            
            for(b=a;b