校OJ 最大m段乘积和最小m段和

乘积和最小m段和"/>

校OJ 最大m段乘积和最小m段和

描述：给一个n位的数和m，代表将n位数分成m段，求最大m段乘积和最小m段和，同样也可以求m段的最小积和最大和，原理一样

刚开始的时候并没有做得出来，因为dp的状态转移方程写错了，还是太嫩了，没有理解好思路，弄了半天原来其实状态方程很好理解，但是用到了n^3，所以没太敢去想太大的复杂度。。。

设dp(i,j)=max(dp(i-1,k)+sum[k+1,j]),其中i表示第i段，j表示已j结尾之前的字符，其实就是寻找前i-1段+在i-1断开之后到j之积最大或和最小，其实还是很好理解的，

思路：

设w(h,t)是S从h位开始的共t位数字组成的十进制数，约定从1开始从左向右对位进行编号，

即最左一位定为第1位。

f(i,j)表示S的前i位数划分成j段后的最大j段乘积。

t(i,j)表示S的前i位数划分成j段后的最小j段和。

无论是f(i,j)还是t(i,j)，这里只考虑i>=j的情况，因为每个段至少1位，因此i必然大于等于j。

显然f(i,j)和t(i,j)都具有最优子结构。

一、最大m段乘积的动态规划递归式

边界： 当j=1时，f(i,1) = w(1,i)， 1<=i<=n    表示当只划分1个段时，最大段乘积

就是从第1位开始共i位数（i>=1）的十进制数值。

当j>=2时，计算f(i,j)的动态规划的递归式如下：

f(i,j) = max{ f(k, j-1) * w(k+1, i-k)    |  k from j-1 to i-1 }      j>=2 && j<=i<=n

(即让k从j-1到i-1变化，找f(k, j-1)和w(k+1, i-k)乘积的最大值)

这个公式这样理解：

当 j>=2 && j<=i<=n 时，现在要求解的问题是前i位划分为j个段的最大j段乘积，

这时考虑前k位，划分j-1个段（因为最后一个段至少占1位，而前j-1个段又至少有j-1位，所以 j-1 <= k <= i-1），

先获得这j-1个段的最大段乘积，再乘以从第k+1位到第i位（共i-k位，这是最后一个段，即第j个段）的十进制数，

让k从j-1到i-1循环，求f(k, j-1)和w(k+1, i-k)乘积的最大值。

二、最小m段和的动态规划递归式

最小m段和公式的分析和最大m段乘积的公式分析是相同的。

边界： 当j=1时，t(i,1) = w(1,i)， 1<=i<=n    表示当只划分1个段时，最小段和就是从第1位开始共i位

数（i>=1）的十进制数值。

当j>=2时，计算t(i,j)的动态规划的递归式如下：

t(i,j) = min{ t(k, j-1) + w(k+1, i-k)    |  k from j-1 to i-1 }      j>=2 && j<=i<=n

(即让k从j-1到i-1变化，找t(k, j-1)和w(k+1, i-k)之和的最小值)

OJ上还需递归回去寻找切割的位置，所以处理起来有点麻烦，但我不太会搜索和递归，所以开多一个数组保存每次切割形成的数，在从后往前找就行了

由于OJ上已经关闭，不能提交了，所以不知有没错，不过在nyoj上提交可以过，但是是不需递归回去的，唉，每次都有资源的时候不好好珍惜，错过了又后悔，但死性不改，到现在还是什么都不懂，弱鸡一个，和别人的差距越来越凸显了，唉，好恨自己。

#include <iostream>using namespace std;
#define N 20
#define inf 9999999
int dp[N][N],fp[N][N];
int a[N],b1[N],b2[N],m,n;
char s[N];int multiply()
{for(int i=2;i<=n;i++){dp[1][i]=dp[1][i-1]*10+a[i];dp[i][i]=dp[i-1][i-1]*a[i];fp[1][i]=dp[1][i];//fp[i][i]=a[i];//}for(int i=2;i<=m;i++){for(int j=i+1;j<=n;j++){dp[i][j]=0;for(int k=i-1;k<j;k++){int ps=0;for(int p=k+1;p<=j;p++)ps=ps*10+a[p];if(dp[i][j]<dp[i-1][k]*ps){dp[i][j]=dp[i-1][k]*ps;fp[i][j]=ps;}}}}/*for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)cout<<dp[i][j]<<"("<<fp[i][j]<<")"<<" ";cout<<endl;}*/return dp[m][n];
}
int sum()
{for(int i=2;i<=n;i++){dp[1][i]=dp[1][i-1]*10+a[i];dp[i][i]=dp[i-1][i-1]+a[i];}for(int i=2;i<=m;i++){for(int j=i+1;j<=n;j++){dp[i][j]=inf;for(int k=i-1;k<j;k++){int ps=0;for(int p=k+1;p<=j;p++)ps=ps*10+a[p];dp[i][j]=min(dp[i-1][k]+ps,dp[i][j]);}}}/*for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)cout<<dp[i][j]<<" ";cout<<endl;}*/return dp[m][n];
}void dfs_multiply()
{b1[m]=fp[m][n];int t=dp[m][n]/fp[m][n];for(int i=m-1;i>=1;i--){for(int j=i;j<=n;j++){if(dp[i][j]==t){b1[i]=fp[i][j];t=dp[i][j]/fp[i][j];break;}}}
}
void dfs_sum()
{b2[m]=fp[m][n];int t=dp[m][n]-fp[m][n];for(int i=m-1;i>=1;i--){for(int j=i;j<=n;j++){if(dp[i][j]==t){b2[i]=fp[i][j];t=dp[i][j]-fp[i][j];break;}}}
}
int main()
{cin>>n>>m>>s;for(int i=0;i<n;i++)a[i+1]=s[i]-'0';fp[1][1]=dp[1][1]=a[1];int p1=multiply();dfs_multiply();int p2=sum();dfs_sum();cout<<p1<<" "<<p2<<endl;for(int i=1;i<=m;i++){if(i==1) cout<<b1[i];else cout<<"*"<<b1[i];}cout<<"="<<p1<<endl;for(int i=1;i<=m;i++){if(i==1) cout<<b2[i];else cout<<"+"<<b2[i];}cout<<"="<<p2<<endl;return 0;
}