NYOJ746――整数划分（四） - c++编程基础

整数划分（四）

时间限制：1000 ms | 内存限制：65535 KB 难度：3

描述

暑假来了，hrdv 又要留学校在参加ACM集训了，集训的生活非常Happy（ps：你懂得），可是他最近遇到了一个难题，让他百思不得其解，他非常郁闷。。亲爱的你能帮帮他吗？

问题是我们经常见到的整数划分，给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积

输入第一行是一个整数T，表示有T组测试数据
接下来T行，每行有两个正整数 n，m ( 1<= n < 10^19, 0 < m <= n的位数)；
输出输出每组测试样例结果为一个整数占一行样例输入

2
111 2
1111 2

样例输出

11
121

来源经典题目

上传者

区间dp，设dp[i][j] 表示在区间[0, i]之中，插入j个乘号可以得到的最大数

设a[i][j]为区间[i,j]所形成的数

所以 dp[i][j] = max(dp[k][j-1] * a[k + 1][i])

注意数的范围，用int不够

#include   
#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; long long dp[22][22]; long long a[22][22]; char str[22]; int main() { int len, t, m; scanf("%d", &t); while (t--) { scanf("%s%d", str, &m); len = strlen(str); m--; memset (a, 0, sizeof(a)); memset (dp, 0, sizeof(dp)); for (int i = 0; i < len; i++) { a[i][i] = str[i] - '0'; for (int j = i + 1; j < len; j++) { a[i][j] = a[i][j - 1] * 10 + str[j] - '0'; } } for (int i = 0; i < len; i++) { dp[i][0] = a[0][i]; } for (int j = 1; j <= m; j++) { for (int i = j; i < len; i++) { for (int k = 0; k < i; k++) { dp[i][j] = max(dp[i][j], dp[k][j - 1] * a[k + 1][i]); } } } printf("%lld\n", dp[len - 1][m]); } return 0; }