68.最大k乘积问题 (15分)
C时间限制：3000 毫秒 | C内存限制：3000 Kb
题目内容：
设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定
的I和k ,求出I的最大k乘积.
Input
输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个n位十进制整数.（n<=10）
Output
输出计算结果，第1行中的数是计算出的最大k乘积.
n位十进制整数.（n<=10）
输入描述
输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个输出描述
输出计算结果，第1行中的数是计算出的最大k乘积.输入样例
2 1
15输出样例
15
用的dfs
n个数字分成 k 段 --> 切 k-1 两个数字之间就两种状态 切还是不切
#include <stdio.h>
#include <string.h> int n, k; int max = -1; char str[11]; int a[11]; // a[i] = 1 表示在第 i 个数字后面要切一刀 void dfs(int pos, int k1){ if(pos >= n || k1 > k) return ; if(k == k1){ int sum = 1; //计算大小 int i = 0; while(str[i] && i < n){ int s = 0; while(a[i] == 0 && i < n){ s = s*10 + (str[i] - ‘0‘); i++; } //循环结束时 a[i] = 1 表示从这里分开 i 是在前面 if(a[i] == 1) s = s*10 + (str[i] - ‘0‘); sum *= s; i++; } if(max < sum) max = sum; return ; } //切一刀 a[pos] = 1; dfs(pos+1, k1+1); a[pos] = 0; //不切 dfs(pos+1, k1); } int main(){ memset(a, 0, sizeof a); scanf("%d%d", &n, &k); scanf("%s", str); if(k == 1){ printf("%s\n", str); } else{ k--; //k 段 只需 k-1 刀 dfs(0, 0); //从第0个数字开始 第0刀 printf("%d\n", max); } return 0; }
原文：https://www.cnblogs.com/DDiamondd/p/10744539.html