- 第五题最大k乘积问题
- 最优解问题,动态规划解决
- 把前i个数字分割成j段,则将前k个数字分成j-1段,将最后i-k个数字作为一段,那么两段的乘积作为前i个数字分割成j段的乘积,从中选取最大值作为f[i][j]的值
- 类似于上面最小m段和问题
- 状态转移方程:f[i][j] = max(f[i][j],f[i - 1][m - 1] * cs(m,j));
- #include <iostream>
- #include <string>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- const int N = 20;
- string s;
- LL f[N][N];
- LL n,k;
- LL cs(int ks,int js){
- LL sum = 0,t = 1;
- for(int i = js;i >= ks;--i){
- sum += (s[i] - '0') * t;
- t *= 10;
- }
- return sum;
- }
- int main(){
- scanf("%lld%lld",&n,&k);
- cin >> s;
- for(int i = 0;i < n;++i) f[0][i] = cs(0,i);
- for(int i = 1;i <= k;++i){
- for(int j = 1;j <= n;++j){
- for(int m = j;m >= i;--m){
- f[i][j] = max(f[i][j],f[i - 1][m - 1] * cs(m,j));
- }
- }
- }
- printf("%d\n",f[k][n - 1]);
- return 0;
- }
[text] asdas
Viewer
Editor
You can edit this paste and save as new:
File Description
- asdas
- Paste Code
- 22 Jun-2021
- 1.08 Kb
You can Share it: