乘积最大-read.ppt

* 问题描述 乘积最大 在一个长度为N的数字串中插入r个乘号，将它分成r+1个部分，找出一种分法，使得这r+1个部分的乘积最大。 * 算法描述 此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i,k]表示在前i位数中插入K个乘号所得的最大值，a[i,j]表示从第i位到第j位所组成的自然数。用f[i,k]存储阶段K的每一个状态，可以得状态转移方程： f[i,k]=max{f[j,k-1]*a[j+1,i]}（k=ji） 边界值：f[j,0]=a[0,j] (0j=i) * 数据说明 int n; //数字的个数 int *p; //存储要划分的数字 int **a; //a[i][j] 表示p[i]到p[j]的数字组成的 //数的大小 int **f; //f[i][j] 表示在前 i 个数字中插入 j 个 //*号乘积的结果 int **s; //s[i][j]表示在前 i 个数字中插入第j //个 * 的位置 * 核心代码 for(i=0;in;i++){ f[i][0]=a[0][i]; s[i][0]=-1; for(k=1;k=i;k++){ f[i][k]=f[k-1][k-1]*a[k][i]; s[i][k]=k-1; for(j=k;ji;j++){ t=f[j][k-1]*a[j+1][i]; if(tf[i][k]) {f[i][k]=t;s[i][k]=j;} } } } * 核心代码 void traceBack(int i,int j){ int t; t=s[i][j]; if(t==-1) { couta[0][i]; return; } traceBack(t,j-1); cout*a[t+1][i]; } *