2013-01-27 08:57:54Morris
[ZJ][高精度DP] d870. NOIP2000 3.乘积最大
內容 ：
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=362) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
輸入說明
：
程序的输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。
輸出說明
：
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
範例輸入 ：
4 2 1231
範例輸出 ：
62
提示
：
出處
：
/**********************************************************************************/
/* Problem: d870 "NOIP2000 3.乘积最大" from NOIP2000普及组第三题、提高组第二题*/
/* Language: CPP (1725 Bytes) */
/* Result: AC(5ms, 435KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-26 16:50:35 */
/**********************************************************************************/
#include <stdio.h>
void multiply(int a[], int b[], int c[]) {
int i, j, k;
for(i = 0; i < 100; i++)
for(j = 0; j < 100; j++)
if(i+j < 100)
c[i+j] += a[i]*b[j];
for(i = 0; i < 100; i++)
if(c[i] >= 10)
c[i+1] += c[i]/10, c[i] %= 10;
}
int compare(int a[], int b[]) {
int i;
for(i = 99; i >= 0; i--)
if(a[i] > b[i])
return 1;
else if(a[i] < b[i])
return 0;
return 1;
}
void assign(int a[], int b[]) {
int i;
for(i = 0; i < 100; i++)
a[i] = b[i];
}
void print(int a[]) {
int i = 99;
while(i >= 1 && a[i] == 0) i--;
while(i >= 0) putchar(a[i]+'0'), i--;
}
int main() {
int N, K, i, j, k, ti, tj;
char s[50];
scanf("%d %d", &N, &K);
scanf("%s", s+1);
K++;
for(i = 1; i <= N; i++)
s[i] -= '0';
int dp[50][10][100] = {};
dp[0][0][0] = 1;
for(i = 1; i <= N; i++) {
for(j = 0; j < K; j++) {
for(k = i; k <= N; k++) {
//dp[k][j+1] = dp[i-1][j]*num[i~>k];
int tmp[100] = {}, num[100] = {};
for(ti = 0, tj = k; tj >= i; ti++, tj--)
num[ti] = s[tj];
multiply(dp[i-1][j], num, tmp); // tmp = dp[i-1][j]*num
/*printf("[%d %d] %d\n", k, j+1, i);
print(dp[i-1][j]);
printf(" * "), print(num), printf(" = "), print(tmp);
puts("\n ========== ");*/
if(!compare(dp[k][j+1], tmp))
assign(dp[k][j+1], tmp);
}
}
}
print(dp[N][K]);
puts("");
return 0;
}