qduoj 30 帅气的HYC求乘积（dfs）

题目地址:点击打开链接

思路：因为数据量比较小，直接搜索枚举放乘号的位置就行。

注意枚举到最后一位数字后别忘了记录下来。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;ll rec[10], ans;int num[25], n, k;bool book[25];void dfs(int cur, ll PRe, int cnt){    if(cnt == k+1 && cur == n+1)    {        ll tmp = 1;        for(int i = 1; i <= k+1; i++)            tmp *= rec[i];        ans = max(ans, tmp);        return ;    }    if(cur > n) return ;    //最后一位不能放    if(cur < n)    {        rec[cnt] = pre*10+num[cur];        dfs(cur+1, 0, cnt+1);    }    //到最后了别忘了要记录最后个数    if(cur == n) rec[cnt] = pre*10+num[cur];    dfs(cur+1, pre*10+num[cur], cnt);}int main(void){    while(cin >> n >> k)    {        for(int i = 1; i <= n; i++)        {            char ch;            scanf(" %c", &ch);            num[i] = ch-'0';        }        ans = 0;        dfs(1, 0, 1);        printf("%lld/n", ans);    }    return 0;}
帅气的HYC求乘积
发布时间: 2015年11月1日 17:02   最后更新: 2015年11月1日 18:38   时间限制: 1000ms   内存限制: 128M
描述
帅气的HYC饿了，于是他定了外卖，但是去拿外卖时却忘了带钱，这可怎么办？于是外卖小哥对他说，我也不为难你，我给你出个题，你要做出来就送你一份免费午餐。题目是这样的：
设有一个长度N的数字串，要求你使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大例如：有一个数字串: 312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62这时，符合题目要求的结果是： 31*2=62
输入
多组测试数据，EOF结束第一行共有2个自然数N,K (1<=N<=19，0<=K<=5)第二行是一个长度为N的数字串。
输出
结果输出到文件，相对于输入，应输出所求得的最大乘积（一个自然数）
样例输入1
4 2 1231样例输出1
62