ICPC最大K乘积报告.docxVIP

最大K乘积解题报告 班级： 姓名 : 学号： 任课老师：徐本柱 2012——2013学年第一学期 课堂内容收获： 本周的ICPC实训，我学习到了在程序设计中有许多原则规范：开放－封闭原则OCP，Liskov 替换原则LSP，依赖倒置原则DIP，接口隔离原则ISP，这些规则可以是我们的程序逻辑更清晰，功能更明确，我们在编写代码中应注意这些规则的应用，程序不是个人的高超技术的劳动成果，他更应是多数人共同合作的产物，所以我们在编写中一定要注意这些规范，令自己的程序易读易懂，养成良好的编写习惯，而在程序设计上，让我认识到程序不是代码的累积，更重要的是代码之间的内在联系，要求这种联系清晰准确，容易读取理解，而且我们应尝试找到解决问题的核心思想，找出问题的核心方法，比如整数的最大K乘积的求解，其核心思想即为MaxI[n][k] = MaxI[w][k-1]×I(w,n-w) 通过该公式，建立递归关系，从而找到解决问题的最佳路径，而且在其中使用动态规划，将该问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，将具体实施划分为若该函数，从而使整个程序显得逻辑清晰，功能明确。 经典DP,绝对经典 hfutoj 1086 Description 设I是一个n位十进制整数I。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。 Input 有多组数据。 输入的第1 行中有1个正整数I,还有一个正整数k,正整数k是分割的段数,I不超过10^19。 Output 计算出的最大k乘积。 Sample Input 15 1 Sample Output 15 问题分析 本题目要对一整型数I，当将其分为K段时，记各段整数乘积为整数I的K乘积，本题即求该数的最大K乘积。 解题思路 对于一整型数I，可将其转化为字符串类型，利用String函数，利于接下来的运算。 由题目进行如下分析： 1.???分析最优解的结构 为方便起见，设I(s,t)是I的由s位开始的t位数字组成的十进制数，R(i,j)表示I(0,i)的j乘积，第j段的起始位置为第w位,有如下关系 R(i,j) = R(w,j-1)×I(w,i-w) ?????? 要使R(i,j)最大，则R(i,j-1)也是最大，所以最大Ｋ乘积问题的最优解包含其子问题的最优解。 2.???建立递归关系 设MaxI[i][j]表???I(0,i)的最大j乘积，则原问题的最优值为MaxI[n][k]。 当k＝1时，MaxI[n][1] = I(0,n); 当k≠1时，可利用最优子结构性质计算MaxI[n][k],?若计算MaxI[n][k]的第k段的起始位置为第w位，则有 MaxI[n][k] = MaxI[w][k-1]×I(w,n-w) 由于在计算时并不知道第k段的起始位置w，所以w还未定。不过w的值只有n-k+1种可能，即k-1=w n。所以MaxI[n][k]可以递归地定义为 MaxI[n][1]=I(0,n)???????k＝1 MaxI[n][k] =max??MaxI[w][k-1]×I(w,n-w)?????????k-1=wn ?k≠1 ? ?MaxI[n][k]给出了最优值，同时还确定了计算最优的断开位置w，也就时说，对于这个w有?????MaxI[n][k] = MaxI[w][k-1]×I(w,n-w) 三、算法： 根据题目动态申请用空间DD，以存放断开的位置，Max用来存储相应的最大K乘积，定义函数conv(int I,int j)用来取以i位开始的j位字符串，并将其转化为整数。定义核心函数solve（int n,int m）,首先初始化部分数组，为了理解方便，Max[][]数组直接从1开始，Max[i][j]表示输入串的求出前i位的最大j乘积。 当k=1时，最大值即为其本身，即为初始化的Max[n][m]。 当k2时，通过循环，首先求出输入串前i位的最大2乘积(i1)，并赋予对应的Max[i][2],当j增长时，MaxI[i][j] = MaxI[w][j-1]×I(w,i-w)(j-1=wi),由于Max[w][j-1]在前一层循环已经计算出，所以以此进行，最终能求出I的最大K乘积Max[n][m]。 具体代码： #includeiostream #includestring using namespace std; int **DD,**Max; string str;//字符串 int conv(int i,int j){ string str1=str.substr(i,j);//取子串 return atoi(str1.c_str());//将string转化为char[]