洛谷P 1018積算最大(dp,高精度)

タイトルの説明
今年は国際数学連盟が確定した「2000―世界数学年」であり、わが国の有名な数学者華羅庚氏の生誕90周年にもふさわしい.華羅庚さんの故郷江蘇金壇で、ユニークな数学知能コンテストの活動を組織し、あなたの親友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=36 2、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向上グループ第二題
明らかにdp問題で、d[i][j]//i番目の数字に乗るときにj乗号を使ったと設定できます.
明らかに,j−1回乗ったときから移行できる.そしてその後はありません.そして乗った数字です.
爆発するlong long.明らかに高精度pythonを使う
PS:初期化時、乗数が役に立たない場合は、最初の文字から現在までの数です
列挙乗数の個数:後の残りの文字を考慮し、各文字を乗算する場合は、最大で使用します.
n-i個の乗数、明らかに前に少なくともu-(n-i)個の乗数(実は直接1個の乗数から
最初の列挙は影響しません.最終的な答えは移行過程で影響を受けないので、強迫症のため、やはりそう書きましょう.
60分のC++コード

#include 
using namespace std;

typedef long long ll;
ll d[50][10];//      ，       
ll get_num(string s)
{
	ll ans = 0;
	int len = s.size();
	for (int i = 0; i < len; i++)
	{
		ans = ans * 10 + s[i] - '0';
	}
	return ans;
}
int main(){
	int n, u;
	cin >> n >> u;
	string s;
	cin >> s;
	s = '0' + s;
	ll sum = 0;
	for (int i = 1; i <= n; i++)
		sum = sum * 10 + s[i] - '0', d[i][0] = sum;
	for (int i = 1; i <= n; i++) //      
	{              
		for (int k = u - (n - i) >= 0 ? u - (n - i) : 1; k < i && k <= u; k++) //       
		{
			for (int j = k; j < i; j++) //  j  
			{
				d[i][k] = max(d[i][k], d[j][k - 1] * get_num(s.substr(j + 1, i - j)));
			}
		}
	}
	cout << d[n][u] << endl;
	return 0;
}

100分のpython

p = [0] * 100
d = [[0 for i in range(55)] for i in range(55)]
n, m = map(int, input().split())
s = input()
s = '0' + s
for i in range(1, n + 1):
    d[i][0] = int(s[1:i + 1])
for i in range(1, n + 1):
    k = (m - (n - i) if (m - (n - i) >= 1) else 1)  
    while k < i and k <= m:
       for j in range(k, i):
           d[i][k] = max(d[i][k], d[j][k - 1] * int(s[j + 1: i + 1]))
       k += 1
print(d[n][m])