QDU 帅气的HYC求乘积
帅气的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=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
多组测试数据，EOF结束
第一行共有2个自然数N,K (1<=N<=19，0<=K<=5)
第二行是一个长度为N的数字串。
结果输出到文件，相对于输入，应输出所求得的最大乘积（一个自然数）
复制
4 2 1231
62
思路：longlong存不下，所以我用了C++大数模板。DFS暴力模拟即可，代码也涉及了STL函数库string的应用。
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
string big_multi(string a, string b)
{
int alen, blen;
alen = a.length(); blen = b.length();
vector<int> tmp(alen+blen-1);
for(int i = 0; i < alen; ++i)
for(int j = 0; j < blen; ++j)
{
tmp[i+j] += (a[i]-'0')*(b[j]-'0');
}
for(int i = tmp.size()-1; i > 0; --i)
{
tmp[i-1] += tmp[i]/10;
tmp[i] %= 10;
}
while(tmp[0] > 9)
{
int k = tmp[0]/10;
tmp[0] %= 10;
tmp.insert(tmp.begin(), k);
}
string ans = "";
for(int i = 0, l = tmp.size(); i < l; ++i)
{
ans += tmp[i] + '0';
}
if(ans[0] == '0') return "0";
return ans;
}
string max(string a, string b)
{
if(a.length() == b.length()) return a > b? a: b;
return a.length() > b.length()? a: b;
}
string dfs(string s, int k)
{
if(k == 0) return s;
string ans = "0", a, b;
for(int i = 1; i <= s.length()-k; ++i)
{
a = s.substr(0, i);
b = dfs(s.substr(i, s.length()), k-1);
ans = max(ans, big_multi(a, b));
}
return ans;
}
int main()
{
string s; int k, n;
while(cin >> n >> k)
{
cin >> s;
cout << dfs(s, k) << endl;
}
return 0;
}
部分大数模板可见: http://blog.csdn.net/yo_bc/article/details/71156030
继续加油~