乘积和最小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;
}
更多推荐
校OJ 最大m段乘积和最小m段和
发布评论