【求助】《乘积最大》 求题解 pascal的 要比较容易看得懂的~~~~

求题解~~神犇路过指点一下~~

没有人么？

神牛啊~~神犇啊~~~救救我吧

我刚写好这个。。～
program chen;
var n,k,i,j,l:integer;
a:array[0..50] of integer;
sum,f:array[0..50,0..50] of int64;
ch:char;
function max(x,y:int64):int64;
begin
if x>y then exit(x) else exit(y);
end;
procedure init;
begin
readln(n,k);
fillchar(sum,sizeof(sum),0);
for i:=1 to n do
begin
read(ch);
val(ch,a[i]);
sum[i,i]:=a[i];
end;
fillchar(f,sizeof(f),0);
for i:=1 to n-1 do
for j:=i+1 to n do
sum[i,j]:=sum[i,j-1]*10+a[j];
for i:=1 to n do
f[0,i]:=sum[1,i];
end;
begin
init;
for i:=1 to k do
for j:=i to n do
for l:=1 to j do
f[i,j]:=max(f[i,j],f[i-1,l]*sum[l+1,j]);
writeln(f[k,n]);
end.


不帮你于心不忍哪

用动态规划求解
设数字串为a1a2a3……an
K=1时，最大值=max{a1 × a2a3…… an, a1 a2 × a3 …… an, ……,a1 a2 a3 …… an-1×an}
此时和穷举法相同。
K=2时，最大值=max{a1 a2a3…… × an-1 × an, a1 a2 a3 …… an-3 × an-2 an-1 × an, ……,a1 × a2 × a3 …… an}


引入记号f(i,j,s)表示ai 到aj，s个乘号取得的最大值，g(i,j)表示从ai到aj的数字列，则上面的公式可以表示为：
K=1时，f(1,n,1)=max{g(1,1)*g(2,n),g(1,2)*g(3,n),…,g(1,n-1)*g(n,n)}
K=2时，f(1,n,2)=max{f(1,n-1,1)*g(n,n),f(1,n-2,1)*g(n-1,n),…,f(1,2,1)*g(3,n)}
一般地：f(1,n,k)=max{f(1,n-1,k-1)*g(n,n),f(1,n-2,k-1)*g(n-1,n),…,f(1,k,k-1)*g(k+1,n)}


一道区间DP，先是读入数据，方法很多，我用的字符串。
积最大，也就是 【在这个字串中加入一些乘号，使积取得最大】。
那么阶段就出来了，如果串中有 i 个乘号，那么再加一个乘号的值只与只有 i 个乘号的时候有关。
也就是，f[i,j],表示在 前 j 的字串里加入 i 个乘号可以取得的最大值


var a:array[1..50] of integer;
g:array[0..50,1..100] of int64;
n,k,i,j,p,s:longint;
max,m:int64;
ch:char;
begin
assign(input,'dtest3.in'); reset(input);
assign(output,'dtest3.out'); rewrite(output);
readln(n,k);
for i:=1 to n do begin read(ch); a[i]:=ord(ch)-48; end;
m:=0;
for i:=1 to n do
begin
m:=m*10+a[i];
g[0,i]:=m;
end;
for i:=1 to k do
for j:=i+1 to n do
begin
max:=0;
for p:=i to j-1 do
begin
m:=0;
for s:=p+1 to j do m:=m*10+a[s];
if m*g[i-1,p]>max then max:=m*g[i-1,p];
end;
g[i,j]:=max;
end;
write(g[k,n]);
close(output); close(output);
end.


状态就是当前的乘积，决策，就是该把乘号放在哪个位置。
因为字串长为 J ，所以可以放在 1和2之间，2和3之间。。。J-1和J 之间。
则，状态转移方程就是 F[I,J]:=MAX(F[I,J],F[I-1,K]*SUM[K+1,J) (1<=k<j)

其中，SUM数组是一个递推的初始化，SUM【I，J】 表示在字串中，由i 到 j 的数字，
如sum【1，1】：=a[i];
sum[1,2]:=sum[1,1]*10+a[2]....
于是，
for i:=1 to n-1 do
for j:=i+1 to n do
sum[i,j]:=sum[i,j-1]*10+a[j];
就可以求出SUM了。也就时任意两个数之间的数值。


多谢神犇~~~~先感谢再看~~

多谢神犇~~~~先感谢再看~~

麻烦神犇~~可不可以把转移方程解释一下？