网站运行费用一般多少,深圳住房城乡建设局网站,英文网站建站公司,湖北建站公司Description 今年是国际数学联盟确定的“2000——世界数学年”#xff0c;又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛#xff0c;组织了一场别开生面的数学智力竞赛的活动#xff0c;你的一个好朋友XZ也有幸得以参加。活动中#xff0c;主…Description 今年是国际数学联盟确定的“2000——世界数学年”又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛组织了一场别开生面的数学智力竞赛的活动你的一个好朋友XZ也有幸得以参加。活动中主持人给所有参加活动的选手出了这样一道题目 设有一个长度为N的数字串要求选手使用K个乘号将它分成K1个部分找出一种分法使得这K1个部分的乘积能够为最大。 同时为了帮助选手能够正确理解题意主持人还举了如下的一个例子 有一个数字串312 当N3K1时会有以下两种分法 1) 3*1236 2) 31*262 这时符合题目要求的结果是31*262 现在请你帮助你的好朋友XZ设计一个程序求得正确的答案。 Input 程序的输入共有两行 第一行共有2个自然数NK6≤N≤401≤K≤6 第二行是一个长度为N的数字串。 Output 相对于输入应输出所求得的最大乘积一个自然数。 Sample Input4 2 1231 Sample Output 62 解题思路 很明显这是一个区间型动规用f[i][j]表示前i个已经插入了j个乘号的最大乘积。 然后为了方便我们可以用数组是s[i][j]表示从第i到j的数。 然后就推出动态转移方程f[i][k]max(f[i][k],f[j][k-1]*s[j1][i]); 这里表示插入第的k个符号前i个数在j处插入乘号。 代码
#includecstdio #includeiostream using namespace std; int n,k; long long s[11][11],f[11][11]; char c; int main() { scanf(%d%d\n,n,k); for (int i1;in;i) { cgetchar(); s[i][i]c-48;//输入 } for (int i1;in;i) for (int ji1;jn;j) { s[i][j]s[i][j-1]*10s[j][j];//自己看思路↑ } for (int i1;in;i) f[i][0]s[1][i];//不插符号时的预处理 for (int ki1;kik;ki)//插入第k个符号 for (int iki1;in;i)//枚举前i个 for (int jki;ji;j)//枚举插入的位置 f[i][ki]max(f[i][ki],f[j][ki-1]*s[j1][i]);
//动态转移方程 printf(%lld,f[n][k]);//输出 }
第二题加法最大
Description 设有一个长度为n的数字字符串分成k1个部份使其k1部份相加的和为最大。例如数字串340670k1其加法有 34067040673 340670704 3406701010 3406703476 34076034076 其最大和为40676。 问题当数字串和k给出后找出一个分法使和为最大。 Sample Input6 1 340670 Sample Output 40673 解题思路 很明显这是一个区间型动规用f[i][j]表示前i个已经插入了j个乘号的最大和。 然后为了方便我们可以用数组是s[i][j]表示从第i到j的数。 然后就推出动态转移方程f[i][k]max(f[i][k],f[j][k-1]s[j1][i]); 这里表示插入第的k个符号前i个数在j处插入加号。 代码
#includecstdio #includeiostream using namespace std; int n,k; long long s[11][11],f[11][11]; char c; int main() { scanf(%d%d\n,n,k); for (int i1;in;i) { cgetchar(); s[i][i]c-48;//输入 } for (int i1;in;i) for (int ji1;jn;j) { s[i][j]s[i][j-1]*10s[j][j];//自己看思路↑ } for (int i1;in;i) f[i][0]s[1][i];//不插符号时的预处理 for (int ki1;kik;ki)//插入第k个符号 for (int iki1;in;i)//枚举前i个 for (int jki;ji;j)//枚举插入的位置 f[i][ki]max(f[i][ki],f[j][ki-1]s[j1][i]);
//动态转移方程 printf(%lld,f[n][k]);//输出 }
