乘积最大

乘积最大noip2003t2 chengji.pas 【问题描述】

今年是国际数学联盟确定的“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

【所属专题】

【适合学习阶段】

【解题思路】 问题分析：

很明显的动态规划。

{ps:考虑到*所加的位置不同，可以导致数字串被分开的位置不同，子串的长度不同，类似于对于数字串加括号，所以应该枚举所有长度l，所有起始位置i的子串，所以使用二位数组d[i，j]存储，长度为0的子串d值为0，长度为1的子串d值为该位数字。

因为要在数字串中加入k个*，考虑如果加入的*大于等于数字串长度，即j-kD[i，j] 当 K=0,s=1231 1 12 123 1231 0 2 23 231 0 0 3 31 0 0 0 1 D[I,j] 当k=1,s=1231 0 2 36 372 0 0 6 62 0 0 0 3 0 0 0 0 D[I,j] 当k=2,s=1231 0 0 6 62 0 0 0 6 0 0 0 0 0 0 0 0 } 令d[i,j,k]为第i个数字到第j个数字加k个乘号所能够达到的最大值。 状态转移方程是：

d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举t, 满足i<=t<=j-1)

{ps:状态转移方程规定所加的第k个*必须在第k-1个*左边的数字串中，因为*没有顺序要求，加在数字串左右都是一样的，因为d[t+1,j,k-1]就是枚举右边加k-1个*后的结果。}

注意到状态转移的时候总是使k减小（或不变）的，所以把k作为阶段来递推（节约空间）。

在每个状态中，l=j-i越来越小，所以从l=0递推到l=n 即：

for k:=1 to c do for l:=0 to n do for i:=1 to n do 递推d[i,j,k]

{ps：使用l即数字串长度从大到小作为数字串的枚举变量，可以根据i计算出来相应的j，达到了枚举i，j的效果}

显然，用两个数组记录d[i,j,k]和d[i,j,k-1],就可以只用两维：d[i,j] 于是算法框架就是(请对照我的源程序)：

{ps:不能看成类似于“邮局”的动态规划，即设c[i,j]代表从1..j的数字串中放i个*，第i个*恰放于j之前的最大乘积值。但是这样不行因为有后效性 例如对于输入 4 2 1231

C[i,j]如下图所示 0 1*2 12*3 123*1 0 0 1*2*3 后效性 }

初始化d1[i,j]

for k:=1 to c do begin

for l:=0 to n do for i:=1 to n do

用d1[i,j](k-1阶段)递推d2[i,j]（k阶段）

d1:=d2; {节省空间，因为递推的时候只与上个阶段有关，故只保留相邻两个阶段} end;

高精度乘法的方法我不是用的模拟手算的过程（这个大家会做吧），而用了类似 多项式乘法的方法，因为我觉得这种写法很好记！(大家仔细看看我的mul过程)

程序在此： const

maxn=40;

ch:array[0..9] of char='0123456789';

v:array['0'..'9'] of integer=(0,1,2,3,4,5,6,7,8,9); type

pbign=^bign;

bign=string[maxn]; var

s:string;

i,j,k,l,n,c,t:integer; x,y:integer; r:bign;

d1,d2:array[1..maxn,1..maxn] of pbign;

procedure mul(a,b:bign; var c:bign); {useful procedure} var

tmp:array[1..maxn*2] of integer; i,j,g,p,k:integer; begin

{init tmp}

while (length(a)>1)and(a[1]='0') do delete(a,1,1); while (length(b)>1)and(b[1]='0') do delete(b,1,1);

p:=length(a)+length(b); for i:=1 to p do tmp[i]:=0;

for i:=1 to length(a) do

for j:=1 to length(b) do {calc like poly!} begin

k:=p-i-j; {how many '0's}

inc(tmp[p-k] ,v[a[i]]*v[b[j]] mod 10); {add here!} inc(tmp[p-k-1],v[a[i]]*v[b[j]] div 10); end;

{update tmp} g:=0; c:='';

for i:=p downto 1 do begin

c:=ch[(tmp[i]+g) mod 10]+c; g:=(tmp[i]+g) div 10; end;

while (length(c)>1)and(c[1]='0') do delete(c,1,1); end;

function bigger(a,b:bign):boolean; var

i:integer; begin

bigger:=true;

if length(a)>length(b) then exit; bigger:=false;

if length(a)b[i] then begin

bigger:=true; exit; end; end;

begin

readln(n,c); readln(s);

for i:=1 to n do for j:=i to n do begin

new(d1[i,j]); new(d2[i,j]);

d2[i,j]^:=copy(s,i,j); end;

for k:=1 to c do

begin

for l:=0 to n do for i:=1 to n do begin j:=i+l;

if j>n then break; d1[i,j]^:='0';

{where to add first '*': t}

for t:=i to j-k do {if t>j-k, there will be too many '*'s! } begin

mul(copy(s,i,t-i+1),d2[t+1,j]^,r); if bigger(r,d1[i,j]^) then d1[i,j]^:=r; end; end;

for i:=1 to n do for j:=1 to n do

d2[i,j]^:=d1[i,j]^; {we use pointers so don't use d2:=d1} end;

writeln(d1[1,n]^); end.

存储结构： 【测试数据】

【源程序】