跳至正文

乘积最大 解题报告

  • OI路程

拿到题目就想到是一个深搜的题目(可能有其他更快的算法,比如什么用数学解的啊,那种。),便开始下手,对所有的情况进行枚举,算出乘值,与ans变量进行比较,比ans大就覆盖ans,否则继续枚举下一种情况,直至全部枚举完。结果忘记考虑会分成0的情况,导致被除数为0!(所以还是提交了两次,乘积最大

等下我还到网上搜搜看有没有什么高效率的算法,我的代码如下:

C语言:

#include <stdio.h>
int n, k;
char str[41];
int tmp = 1, ans = 0;

void srch(int now, int count, int sum)
{
 if(now == n || count == k){
 int i;
 for(i = now; i < n; i++){
 sum *= 10;
 sum += str[i] - \'0\';
 }
 if(count == k && tmp * sum > ans){
 ans = tmp * sum;
 }
 return ;
 }
 if(sum != 0){ //忘记考虑sum为0的情况了 
 tmp *= sum;
 srch(now + 1, count + 1, str[now] - \'0\');
 tmp /= sum; //被除数不能为0 
 }
 srch(now + 1, count, sum * 10 + str[now] - \'0\');
}

int main(void)
{
 scanf(%d%d\\n, &n, &k);
 scanf(%s, str);
 srch(1, 0, str[0] - \'0\');
 printf(%d\\n, ans);
 return 0;
}

到网上找到了动态规划解法,等我看完了再发上来。
实在是看不懂,不看算了,因为发现NOIP2000提高组里也有一个乘积最大,那个时候我再仔细看吧。

发表回复

您的电子邮箱地址不会被公开。