最大k乘积问题（dp)

Problem 1208 最大k乘积问题

Accept: 356    Submit: 828 Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。 对于给定的I和k，编程计算I的最大k乘积。

 Input

输入文件由多组数据组成。每组数据格式如下： 第1行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的断数。 接下来的一行中是一个n位十进制整数。（n<=10）

 Output

对于每组数据，输出计算出的最大k乘积。

 Sample Input

2 115

 Sample Output

15

解题思路：

1.输入

输入的时候采用的方式是先用char输入，然后把每一位转换成数字存储在a数组中。

2.初始化

用一个二维数组m[ i ][ j ]来存储，其表示的是存放 i 到 j 所表示的整数。

定义dp[ i ][ j ]前i 个数分成 j 段的最大乘积，所以dp[ i ][ 1 ]=m[ 1 ][ i ]，因为只分一段，也就是直接从第一位到i 位数字。

3.动态规划过程

思路是把前 i 个数字分割成 j 段，则将前 k 个数字分成 j-1段，将最后i - k个数字作为一段，那么两段的乘积作为前 i 个数字分割成 j 段的乘积，从中选取最大值作为dp[ i ][ j ]的值。

此时，k 个数字分成 j-1段位：dp[ k ][ j-1]，将最后i-k个数字作为一段：m[k+1][ i ] （即从k + 1到 i 所代表的数）

即： dp[ i ][ j ]=max{dp[ i ][ j ] , dp[ k ][ j-1]*m[ k+1][ i ]}

#include <cstdio> #include <cstring> #include <iostream> using namespace std; int dp[20][20]; int main() { int n,k,a[20],m[20][20]; while(scanf("%d%d",&n,&k)!=EOF) { for(int i=1;i<=n;i++) { char ch; cin>>ch; a[i]=ch-'0'; } memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { m[i][i]=a[i]; } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { m[i][j] = m[i][j-1]*10 + m[j][j]; } } for(int i=1;i<=n;i++) { dp[i][1] = m[1][i]; } for(int i=1;i<=n;i++)//位数 { for(int j=0;j<i;j++)//分割段数 { for(int k=1;k<i;k++) { dp[i][j]=max(dp[i][j],dp[k][j-1]*m[k+1][i]); } } } cout<<dp[n][k]<<endl; } return 0; }