pascal乘积最大问题

我们一起来分析一下：
设字符串长度为n，乘号数为k，如果n=50,k=1时，
有（n-1）=49种不同的乘法，当k=2时，有C(2，50-1)=1176种乘法，既C(k,n-1)种乘法，当n、k稍微大一些的时候，用穷举的方法就不行了。
设数字字符串为a1a2…an
K=1时：一个乘号可以插在a1a2…an中的n-1个位置，这样就得到n-1个子串的乘积：
a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an (这相当于是穷举的方法)
此时的最大值=max{a1*a2…an, a1a2*a3…an, … , a1a2…a n-1*an }
K=2时，二个乘号可以插在a1a2…an中n-1个位置的任两个地方， 把这些乘积
分个类，便于观察规律：
①倒数第一个数作为被乘数：
a1*a2 …a n-3 a n-2 a n-1*an，
a1a2 …*a n-2 a n-1*an，
a1a2 …*a n-1*an。
设符号F[n-1,1]为在前n-1个数中插入一个乘号的最大值,则的最大值为
F[n-1,1]*an。
②倒数第二个数作为被乘数：
a1*a2 …an-3 a n-2* a n-1，
an … a1a2 …*a n-2*a n-1an，
a1a2…*a n-3 a n-2* a n-1 an。
设符号F[n-2,1]为在前n-2个数中插入一个乘号的最大值,则的最大值为
F[n-2,1]*a n-1 an
③倒数第三个数作为被乘数：
…
设符号F[n-3,1]为在前n-3个数中插入一个乘号的最大值,则的最大值为
F[n-3,1]*a n-2 a n-1 an
……
a3~an作为被乘数：F[2,1]*a3 …a n-2 a n-1 an
此时的最大乘积为：
F[n,k]=max{F[n-1]*an，F[n-2,1]*a n-1 an，
F[n-3,1]*a n-2 a n-1 an，
F[2,1]*a3 …a n-2 a n-1 an}
设F[i,j]表示在 i 个数中插入 j 个乘号的最大值，g[i,j]表示从ai到aj的数字列，则可得到动态转移方程：
F[i,j] = max{F[i-1,j-1]*g[i,i], F[i-2,j-1]*g[i-1,i],
F[i-3,j-1]*g[i-2,i], …., F[j,j-1]*g[j+1,i]}
(1<=i<=n, 1<=j<=k)
边界： F[i,0] =g[1,i] （数列本身）
阶段：子问题是在子串中插入j-1,j-2……1,0个乘号，因此乘号个数作为阶段的划分（j个阶段）
状态：每个阶段随着被乘数数列的变化划分状态。
决策：在每个阶段的每种状态中做出决策。
数据结构：
（此题不需要高精度，Pascal用longint即可AC)
int n,k; /* n为数字个数，k为划分个数*/
int i,j,l; /*循环变量*/
char c; /*字符读入*/
int data[50]={0}; /*存数字的数组*/
int g[50][50],f[50][10]; /*g为数字列，f为动态规划数组*/
初始化：
cin >> n >> k; /*读入,n,k*/
for(i=1;i<=n;i++)
{
cin >> c; /*读入一个数字*/
data[i]=c-'0'; /*字符转化数字*/
g[i][i]=data[i];/*初始化数列*/
}
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
g[i][j]=g[i][j-1]*10+data[j]; /*初始化数列*/
for(i=1;i<=n;i++)
f[i][0]=g[1][i]; /*初始化动态规划数组*/
动态规划：
for(i=1;i<=n;i++)/*方程：f[i,j]表示前i个数中插入j个*号的最优值。*/
for(j=1;j<=i+1;j++)
for(l=1;l<=i-1;l++)
f[i][j]=max(f[i][j],f[l][j-1]*g[l+1][i]);
输出f[n][k]

1楼的解答太深奥了，看不懂啊。能不能搞点容易懂的算法。

这是动规题
并且是NOIP上 吧
不难
看看题解就知道了

用动归啦