[text] asdas

Viewer

  1.  
  2. 第五题最大k乘积问题
  3.  
  4.  
  5. 最优解问题,动态规划解决
  6. 把前i个数字分割成j段,则将前k个数字分成j-1段,将最后i-k个数字作为一段,那么两段的乘积作为前i个数字分割成j段的乘积,从中选取最大值作为f[i][j]的值
  7. 类似于上面最小m段和问题
  8. 状态转移方程:f[i][j] = max(f[i][j],f[i - 1][m - 1] * cs(m,j));
  9.  
  10. #include <iostream>
  11. #include <string>
  12. #include <cstdio>
  13. #include <algorithm>
  14. using namespace std;
  15. typedef long long LL;
  16. const int N = 20;
  17. string s;
  18. LL f[N][N];
  19. LL n,k;
  20.  
  21. LL cs(int ks,int js){
  22.     LL sum = 0,t = 1;
  23.     for(int i = js;i >= ks;--i){
  24.         sum += (s[i] - '0') * t;
  25.         t *= 10;
  26.     }
  27.     return sum;
  28. }
  29.  
  30. int main(){
  31.     scanf("%lld%lld",&n,&k);
  32.     cin >> s;
  33.     for(int i = 0;i < n;++i)    f[0][i] = cs(0,i);
  34.     for(int i = 1;i <= k;++i){
  35.         for(int j = 1;j <= n;++j){
  36.             for(int m = j;m >= i;--m){
  37.                 f[i][j] = max(f[i][j],f[i - 1][m - 1] * cs(m,j));
  38.             }   
  39.         }
  40.     }
  41.     printf("%d\n",f[k][n - 1]);
  42.     return 0;
  43. }

Editor

You can edit this paste and save as new: