文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > ICPC最大K乘积报告
侵权投诉

ICPC最大K乘积报告

C++

Sample Input

15 1

Sample Output

15

1. 问题分析

本题目要对一整型数I,当将其分为K段时,记各段整数乘积为整数I的K乘积,本题即求该数的最大K乘积。

2. 解题思路

对于一整型数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)也是最大,所以最大K乘积问题的最优解包

含其子问题的最优解。

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<=w<n 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位字符串,并将其转化

上一页第2页

你可能喜欢

热门文档

相关文档

  • 《Thimbles》解题报告

    比赛(解题报告) 8页 免费 《乘积最大》解题报告 28页 免费 Per的解题报告 ...【题目来源】 ACM ICPC 2004-2005, NEERC, Southern Subregional Contest Saratov...

  • 杭电ACM2000-2019

    Problem Description 给你 n 个整数,求他们中所有奇数的乘积。 Input 输入数据...(k) sum++; } if(sum==y-x+1) printf("OK\n"); else printf("...

  • 浙江师范大学第10届ACM竞赛解题报告

    浙江师范大学第10届ACM竞赛解题报告_理学_高等教育_教育专区。ACM的看看哦...(T<=10),第二行开始,每组测试数据先给出 N,K,然 后是另起一行 N 个...

  • ACM程序设计试题

    而空 格字符与其它任意字符之间的距离为已知的定值 K,空格字符与空格字符的...任务是寻找这 m 个数的 非空子集的个数 x,使得每个子集的乘积都是一个完全...

  • acm复习

    } return 0; } 求奇数的乘积 Time Limit:1000MS Memory Limit:65536K Total Submit:2765 Accepted:1801 Description 给你 n 个整数,求他们中所有奇数的乘积。...

  • ACM练习题

    Yn 第 3 行: K 第 4 ~ K+1 行: ( Xi ...安 全系数等于所经过的各个电缆上的安全系数的乘积...2014年度细分行业报告汇集 2014年移动互联网O2O分析...

  • 数论算法--ACM

    基本定理:每个正整数都可以唯一地表示成素数的乘积。...Euler定理 若(k,m)=1,则kf(m) ≡1(mod m) ...2014年细分行业研究报告年度盘点 2014年移动互联网O2O...

  • 北京大学ACM,1001题详细解答

    (与k 考虑k+t个单精度数相乘 考虑k+t个单精度数相乘 a1*a2*…*ak *ak... 北京大学poj1001解题报告... 33页 1下载券 北大ACM题分类 9页 2下载券...

  • ACM 矩阵操作

    Strassen算法(求两个n*n的矩阵的乘积) O(nLog7)...[子式]n阶矩阵An*n,我们顺序选择任意的k行与k列... 9月21日ACM作业解题报告 暂无评价 9页 免费 喜欢...

  • 备战ACM实验题目

    (11)ACM-ICPC:http://icpc.baylor.edu/icpc/ (...叉积 / 面积 解析几何的主力:复数 基本形 点 ....81.202/course/problemSolving/ 可以找到解题报告。...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email