下载文档原格式
OpenJudge解题经验交流1.1编程基础之输⼊输出01:Hello, World!02:输出第⼆个整数PS：a，b需⽤longint类型接收03:对齐输出04:输出保留3位⼩数的浮点数05:输出保留12位⼩数的浮点数08:字符三⾓形09:字符菱形10:超级玛丽游戏1.2编程基础之变量定义、赋值及转换01:整型数据类型存储空间⼤⼩02:浮点型数据类型存储空间⼤⼩PS：可利⽤sizeof函数03:其他基本数据类型存储空间⼤⼩04:填空：类型转换105:填空：类型转换206:浮点数向零舍⼊07:打印ASCII码08:打印字符09:整型与布尔型的转换PS：n需要⽤longint类型接收10:Hello, World!的⼤⼩PS：字符串最后有⼀个结束标志'\0'，所以实际长度要再加11.3编程基础之算术表达式与顺序执⾏01:A+B问题PS：A，B需⽤longint类型接收02:计算(a+b)*c的值03:计算(a+b)/c的值04:带余除法05:计算分数的浮点数值06:甲流疫情死亡率07:计算多项式的值08:温度表达转化09:与圆相关的计算10:计算并联电阻的阻值12:计算球的体积13:反向输出⼀个三位数14:⼤象喝⽔16:计算线段长度17:⽤边长求三⾓形⾯积PS：海伦公式18:计算三⾓形⾯积19:A*B问题20:计算2的幂1.4编程基础之逻辑表达式与条件分⽀01:判断数正负02:输出绝对值03:奇偶数判断04:奇偶ASCII值判断05:整数⼤⼩⽐较06:判断是否为两位数07:收集瓶盖赢⼤奖08:判断⼀个数能否同时被3和5整除09:判断能否被3，5，7整除10:有⼀门课不及格的学⽣11:晶晶赴约会12:骑车与⾛路13:分段函数PS：N需定义为single类型14:计算邮资15:最⼤数输出PS：三个整数需⽤longint接收16:三⾓形判断PS：输⼊的三⾓形三条边长不⼀定是从⼩到⼤排好序的，⽽是随机给的17:判断闰年18:点和正⽅形的关系19:简单计算器1.5编程基础之循环控制01:求平均年龄02:均值03:求整数的和与均值PS：样例输⼊有误，n个整数是在⼀⾏⾥⾯，⽽不是n⾏04:最⾼的分数05:整数序列的元素最⼤跨度值06:奥运奖牌计数08:满⾜条件的数累加09:整数的个数10:与指定数字相同的数的个数11:乘⽅计算12:⼈⼝增长问题13:菲波那契数列PS：k等于1和2的情况需单独考虑15:鸡尾酒疗法16:救援18:⾓⾕猜想PS：运算的过程会超出longint范围19:津津的储蓄计划20:药房管理21:正常⾎压22:求特殊⾃然数PS：数据进制转换23:统计满⾜条件的4位数个数24:级数求和25:分离整数的各个数位26:数字反转27:含k个3的数28:开关灯29:求分数序列和PS：p、q会达到longint级别30:计算分数加减表达式的值31:求阶乘的和32:求出e的值33:计算多项式的值34:与7⽆关的数35:数1的个数36:数字统计37:画矩形38:质因数分解39:第n⼩的质数PS：第10000⼩的质数是104729 40:⾦币t1392:Bank Interestt2757:多边形内⾓和PS：while not eoln dot6:Financial Management1.6编程基础之⼀维数组01:与指定数字相同的数的个数02:陶陶摘苹果03:计算书费04:数组逆序重放PS：第⼆⾏的n个整数需⽤longint类型接收05:年龄与疾病06:校门外的树07:向量点积计算08:⼤整数加法09:计算2的N次⽅PS：⾼精度乘⽅，2的100次⽅是⼀个30位整数a1738:⼤整数减法t1577:Jolly Jumpers1.7编程基础之字符串01:统计数字字符个数02:找第⼀个只出现⼀次的字符04:⽯头剪⼦布05:输出亲朋字符串06:合法 C 标识符08:密码翻译09:潜伏者11:将字符串中的⼩写字母转换成⼤写字母12:⼤⼩写字母互换13:整理药名16:删除单词后缀25:ISBN号码28:判断字符串是否为回⽂1.8编程基础之多维数组01:矩阵交换⾏PS：矩阵中的数字需⽤integer类型接收02:同⾏列对⾓线的格⼦03:计算矩阵边缘元素之和PS：如果不⽤数组应该怎么做？04:错误探测PS：此题不能⽤while not eof do begin05:计算鞍点06:图像相似度07:矩阵加法08:矩阵乘法09:矩阵转置10:图像旋转12:图像模糊处理13:扫雷游戏地雷数计算15:肿瘤⾯积1.9编程基础之顺序查找01:查找特定的值02:输出最⾼分数的学⽣姓名03:不⾼兴的津津04:谁拿了最多奖学⾦05:最⼤值和最⼩值的差06:笨⼩猴07:不与最⼤数相同的数字之和PS：如果不⽤⼀维数组应该怎么做？09:直⽅图12:最长平台PS：平台中的数有负数的情况13:整数去重15:接⽔问题t1798:数字求和1.10编程基础之简单排序01:谁考了第k名02:奇数单增序列03:成绩排序04:奖学⾦05:分数线划定PS：注意排好序后划定分数线时请考虑同分并列的情况06:整数奇偶排序PS：10个数中有可能会有相同的数噢09:明明的随机数1.12编程基础之函数与过程抽象01:简单算术表达式求值02:短信计费03:甲流病⼈初筛04:最匹配的矩阵05:统计单词数06:寻宝07:机器翻译08:Vigenère密码PS：注意是根据密钥和密⽂求明⽂09:图像旋转翻转变换10:素数对1.13编程基础之综合应⽤03:⼤整数减法05:素数回⽂数的个数07:玛雅历09:⼤整数乘法PS：⼆个200位⼤数相乘结果可能达到400位10:判决素数个数PS：X可能会⼩于Y14:求满⾜条件的3位数PS：实际满⾜条件的3位数有9个22:因⼦分解25:计算两个⽇期之间的天数27:除以1328:出现次数超过⼀半的数PS：超过⼀半是指超过n的⼀半2.1基本算法之枚举1752:鸡兔同笼1809:两倍1812:完美⽴⽅1943:满⾜条件的整数2722:和数2723:因⼦问题3526:最简真分数PS：最简真分数组合的个数最⼤可达longint级6175:细菌的战争PS：公式的写法有讲究，g:=trunc(g+g*5/100);可以AC，但如果写成g:=trunc(g*1.05);就AC不了6184:找和为K的两个元素PS：⽤类似选择排序的双重循环穷举6187:称体重6188:⽐饭量7621:硬币⾯值组合PS：输出顺序为：先按c的值从⼩到⼤，若c相同则按b的值从⼩到⼤。
动态规划是对最优化问题的一种新的算法设计方法。
由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。
不存在一种万能的动态规划算法。
但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。
多阶段决策过程最优化问题——动态规划的基本模型在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。
当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。
【例题1】最短路径问题。
图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。
现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。
用dk(x k，x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k到终点E的最短距离，利用倒推方法求解A到E的最短距离。
具体计算过程如下：S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3S2: K=3，有：F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8F3(C2)=d3(C2,D1)+f4(D1)=5+3=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2: K=2，有：F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)}=min {9,12,14}=9F2(m)=min{d2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)}=min{16,10}=10S4：k=1，有：F1(A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}=min{13,13}=13因此由A点到E点的全过程的最短路径为A—>B2一>C4—>D3—>E。
动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。
动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。
它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。
1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。
2.定义状态：确定存储子问题解的状态变量和状态方程。
3.确定边界条件：确定初始子问题的解，也称为边界状态。
4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。
5.求解最优解：通过遍历状态变量找到最优解。
1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。
可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。
2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。
给定一个序列，找到其中最长的递增子序列。
可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。
3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。
给定一系列矩阵，求解它们相乘的最小计算次数。
可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。
4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。
可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。
动态规划算法的详细原理及使用案例一、引言动态规划是一种求解最优化问题的算法，它具有广泛的应用领域，如机器学习、图像处理、自然语言处理等。
本文将详细介绍动态规划算法的原理，并提供一些使用案例，以帮助读者理解和应用这一算法的具体过程。
二、动态规划的基本原理动态规划算法通过将问题分解为多个子问题，并利用已解决子问题的解来求解更大规模的问题。
其核心思想是利用存储技术来避免重复计算，从而大大提高计算效率。
具体来说，动态规划算法通常包含以下步骤：1. 定义子问题：将原问题分解为若干个子问题，这些子问题具有相同的结构，但规模更小。
这种分解可以通过递归的方式进行。
2. 定义状态：确定每个子问题的独立变量，即问题的状态。
状态具有明确的定义和可计算的表达式。
3. 确定状态转移方程：根据子问题之间的关系，建立状态之间的转移方程。
这个方程可以是简单的递推关系式、递归方程或其他形式的方程。
4. 解决问题：使用递推或其他方法，根据状态转移方程求解每个子问题，直到获得最终解。
三、动态规划的使用案例1. 背包问题背包问题是动态规划算法的经典案例之一。
假设有一个背包，它能容纳一定重量的物品，每个物品有对应的价值。
目的是在不超过背包总重量的前提下，选取最有价值的物品装入背包。
这个问题可以通过动态规划算法来求解。
具体步骤如下：（1）定义问题：在不超过背包容量的限制下，选取物品使得总价值最大化。
（2）定义状态：令dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值。
（3）状态转移方程：dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])，其中w[i]为第i个物品的重量，v[i]为第i个物品的价值。
（4）解决问题：根据状态转移方程依次计算每个子问题的解，并记录最优解，直到获得最终答案。
2. 最长公共子序列最长公共子序列（Longest Common Subsequence，简称LCS）是一种经典的动态规划问题，它用于确定两个字符串中最长的共同子序列。
动态规划算法
动态规划算法（Dynamic Programming）是一种解决多阶段最优化决策问题的算法。
它将问题分为若干个阶段，并按照顺序从第一阶段开始逐步求解，通过每一阶段的最优解得到下一阶段的最优解，直到求解出整个问题的最优解。
动态规划算法的核心思想是将问题划分为子问题，并保存已经解决过的子问题的解，以便在求解其他子问题时不需要重新计算，而是直接使用已有的计算结果。
即动态规划算法采用自底向上的递推方式进行求解，通过计算并保存子问题的最优解，最终得到整个问题的最优解。
动态规划算法的主要步骤如下：
1. 划分子问题：将原问题划分为若干个子问题，并找到问题之间的递推关系。
2. 初始化：根据问题的特点和递推关系，初始化子问题的初始解。
3. 递推求解：按照子问题的递推关系，从初始解逐步求解子问题的最优解，直到求解出整个问题的最优解。
4. 得到最优解：根据子问题的最优解，逐步推导出整个问题的最优解。
5. 保存中间结果：为了避免重复计算，动态规划算法通常会使
用一个数组或表格来保存已经求解过的子问题的解。
动态规划算法常用于解决最优化问题，例如背包问题、最长公共子序列问题、最短路径问题等。
它能够通过将问题划分为若干个子问题，并通过保存已经解决过的子问题的解，从而大大减少计算量，提高算法的效率。
总之，动态规划算法是一种解决多阶段最优化决策问题的算法，它通过将问题划分为子问题，并保存已经解决过的子问题的解，以便在求解其他子问题时不需要重新计算，从而得到整个问题的最优解。
动态规划算法能够提高算法的效率，是解决最优化问题的重要方法。
动态规划算法动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的；动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策。
需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。
必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。
一、动态规划基本思想（一）基本概念描述阶段的变量称为阶段变量k。
阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。
表示每个阶段开始所处的自然状况或客观条件。
通常一个阶段有若干个状态，描述过程状态的变量称为状态变量Sk。
某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策，描述决策的变量成为决策变量Uk。
在实际问题中决策变量取值一般在一个范围，称之为允许决策集合（策略）。
状态转移方程：Sk+1 = Tk（Sk，?Uk）4、指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，为指标函数。
指标函数常见的形式：（1）各段指标的和的形式（2）各段指标的积的形式其中表示第j阶段的阶段指标（二）基本思想动态规划方法的关键：正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。
要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。
即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。
二、建立动态规划模型的步骤划分阶段：按时间或空间先后顺序，将过程划分为若干相互联系的阶段。
对于静态问题要人为地赋予“时间”概念，以便划分阶段。
正确选择状态变量：选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。
2.6基本算法之动态规划01（）1775:采药总时间限制:1000ms内存限制:65536kB描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。
”如果你是辰辰，你能完成这个任务吗？输入输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入70 371 10069 11 2样例输出3来源NOIP 20051944:吃糖果总时间限制:1000ms内存限制:65536kB描述名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有N 块巧克力，20 > N >0）。
妈妈告诉名名每天可以吃一块或者两块巧克力。
假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。
例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。
现在给定N，请你写程序求出名名吃巧克力的方案数目。
输入输入只有1行，即整数N。
输出输出只有1行，即名名吃巧克力的方案数。
样例输入样例输出6252:带通配符的字符串匹配总时间限制:1000ms内存限制:65536kB描述通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。
通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。
你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。
例如，1?456 可以匹配12456、13456、1a456，但是却不能够匹配23456、1aa456；2*77?8可以匹配24457798、237708、27798。
输入输入有两行，每行为一个不超过20个字符的字符串，第一行带通配符，第二行不带通配符输出如果两者可以匹配，就输出“matched”，否则输出“not matched”样例输入样例输出666:放苹果总时间限制:1000ms内存限制:65536kB描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入第一行是测试数据的数目t（0 <= t<= 20）。
以下每行均包含二个整数M 和N，以空格分开。
1<=M，N<=10。
输出对输入的每组数据M和N，用一行输出相应的K。
样例输入样例输出7614:最低通行费总时间限制:1000ms内存限制:65536kB描述一个商人穿过一个N*N 的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。
每穿越中间1个小方格，都要花费1个单位时间。
商人必须在(2N-1)个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入第一行是一个整数，表示正方形的宽度N (1 <= N < 100)；后面N 行，每行N 个不大于100的整数，为网格上每个小方格的费用。
输出至少需要的费用。
样例输入样例输出提示样例中，最小值为109=1+2+5+7+9+12+19+21+ 33。
7624:山区建小学总时间限制:1000ms内存限制:65536kB描述政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。
已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。
为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设0 < n < = m < 500 ）。
请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
输入第1行为m和n，其间用空格间隔第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如10 32 4 6 5 2 43 1 3表示在10个村庄建3所学校。
第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。
输出各村庄到最近学校的距离之和的最小值。
样例输入样例输出7625:三角形最佳路径问题总时间限制:1000ms内存限制:65536kB描述如下所示的由正整数数字构成的三角形:73 88 1 02 7 4 44 5 2 6 5从三角形的顶部到底部有很多条不同的路径。
对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。
你的任务就是求出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的下边（正下方）的数或者右边（右下方）的数。
输入第一行为三角形高度100>=h>=1，同时也是最底层边的数字的数目。
从第二行开始，每行为三角形相应行的数字，中间用空格分隔。
输出最佳路径的长度数值。
样例输入样例输出提示如何采用动态规划的思想，对问题进行分解。
8780:拦截导弹总时间限制:1000ms内存限制:65536kB描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹。
输入第一行是一个整数N（不超过15），表示导弹数。
第二行包含N个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）。
输出一个整数，表示最多能拦截的导弹数。
样例输入样例输出8782:乘积最大总时间限制:1000ms内存限制:65536kB描述今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。
在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。
活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：1) 3*12=362) 31*2=62这时，符合题目要求的结果是：31*2=62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入程序的输入共有两行：第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）第二行是一个长度为N的数字串。
输出输出所求得的最大乘积（一个自然数）。
（保证最终答案不超过int范围）样例输入样例输出来源NOIP2000复赛普及组第三题。
