这题用DP或者DFS均能过。 在COJ上看了ahyangyi大神的代码,手写了个bigint的结构体,遂模仿之,果然很好使
典型的DP问题
设w(h,q)表示从h位开始的q位数字组合所成的十进制数,m(i,j)表示前i位数字串插入j个乘号所得的最大乘积,初始值为:
m(i,0) = w(0,q) ;
动规方程如下所示:
if (j==0) m(i,j) = w(0,i) ;
else if(j>0)
m(i,j) = max { m(d,j-1)*w(d+1,i-d) } ps: 其中 0<= d < i
下标均从0开始
DP版本
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 100005
#define eps 1e-10
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct BigInteger
{
int len;
int d[105];
BigInteger(){len = 1; d[0] = 0;}
BigInteger(string s)
{
len = s.length();
reverse(s.begin(), s.end());
for(int i = 0; i < len; i++)
d[i] = s[i] - '0';
while(len > 0 && d[len - 1] == 0) len--;
if(!len) d[len++] = 0;
}
void operator *=(const BigInteger &a)
{
int tmp[105];
for(int i = 0; i < len + a.len; i++) tmp[i] = 0;
for(int i = 0; i < len; i++)
for(int j = 0; j < a.len; j++)
tmp[i + j] += d[i] * a.d[j];
len = len + a.len - 1;
for(int i = 0; i < len; i++)
{
tmp[i + 1] += tmp[i] / 10;
tmp[i] %= 10;
}
if(tmp[len]) len++;
for(int i = 0; i < len; i++) d[i] = tmp[i];
while(len > 0 && d[len - 1] == 0) len--;
if(!len) d[len++] = 0;
}
bool operator <(const BigInteger &a)const
{
if(len != a.len) return len < a.len;
for(int i = len - 1; i >= 0; i--)
if(d[i] != a.d[i]) return d[i] < a.d[i];
return false;
}
void out()
{
for(int i = len - 1; i >= 0; i--)
printf("%d", d[i]);
printf("\n");
}
}dp[55][11];
int n, m;
char s[105];
int main()
{
scanf("%d%d%s", &n, &m, s);
string tx = s;
for(int i = 0; i < n; i++)
{
dp[i][0] = BigInteger(tx.substr(0, i + 1));
for(int j = 1; j <= m; j++)
{
for(int k = 0; k < i; k++)
{
BigInteger q(tx.substr(k + 1, i - k));
q *= dp[k][j - 1];
if(dp[i][j] < q) dp[i][j] = q;
}
}
}
dp[n - 1][m].out();
return 0;
}
DFS版本
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 100005
#define eps 1e-10
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct BigInteger
{
int len;
int d[105];
BigInteger(){len = 1; memset(d, 0, sizeof(d)); d[0] = 1;}
BigInteger(string s)
{
len = s.length();
for(int i = 0; i < len; i++)
d[i] = s[i] - '0';
while(len > 0 && d[len - 1] == 0) len--;
if(!len) d[len++] = 0;
}
void operator *=(const BigInteger &a)
{
int tmp[105];
for(int i = 0; i < len + a.len; i++) tmp[i] = 0;
for(int i = 0; i < len; i++)
for(int j = 0; j < a.len; j++)
tmp[i + j] += d[i] * a.d[j];
len = len + a.len - 1;
for(int i = 0; i < len; i++)
{
tmp[i + 1] += tmp[i] / 10;
tmp[i] %= 10;
}
if(tmp[len]) len++;
for(int i = 0; i < len; i++) d[i] = tmp[i];
while(len > 0 && d[len - 1] == 0) len--;
if(!len) d[len++] = 0;
}
bool operator <(const BigInteger &a)const
{
if(len != a.len) return len < a.len;
for(int i = len - 1; i >= 0; i--)
if(d[i] != a.d[i]) return d[i] < a.d[i];
return false;
}
void out()
{
for(int i = len - 1; i >= 0; i--)
printf("%d", d[i]);
printf("\n");
}
}ans;
int n, k;
char s[105];
void dfs(BigInteger t, int m, int x)
{
if(m == 0)
{
if(ans < t) ans = t;
return;
}
for(int i = x ; i < n - m + 1; i++)
{
BigInteger q = t;
string fk = s;
fk = fk.substr(x, i - x + 1);
reverse(fk.begin(), fk.end());
q *= BigInteger(fk);
dfs(q, m - 1, i + 1);
}
}
int main()
{
scanf("%d%d%s", &n, &k, s);
ans.d[0] = 0;
BigInteger t;
dfs(t, k + 1, 0);
ans.out();
return 0;
}
分享到:
相关推荐
#### c/c++语言环境测试 **接下来我们打开postman进行测试已post形式发送请求http://IP:5050/run携带参数** ~~~java { "cmd": [{ "args": ["/usr/bin/g++", "Main.cc", "-o", "a"], "env": ["PATH=/usr/bin:/...
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。...蓝桥杯OJ部分题目及源码+项目说明.zip
BJFU-OJ实验
Leverage 是一个在线的评测系统。系统提供了题目供使用者练习编程能力与算法技巧。另外系统也有完善的比赛与作业系统供日常教学、比赛选拔所用。用户需要提交题目的由程序语言实现的解法,由评测系统进行自动地评测...
1296: a/b + c/d 时间限制: 1 Sec 内存限制: 128 MB 提交: 213 解决: 135 [提交] [状态] [讨论版] [命题人:外部导入] 题目描述 给你2个分数,求他们的和,并要求和为最简形式。 输入 输入首先包含一个正整数T(T)...
OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目
OJ原始码 C,C ++和Java描述 OJ指导:
北邮java课程作业OJ黑杰克,已AC
the DOS / Win XP/2000/NT/9x distribution (COMPLEX Numbers): mapmx100.zip
Peking OJ 1001题 附有测试数据
针对刚学习动态规划算法 贪心算法的题目 北航编程啦的若干经典例题
标题:乘积最大 给定N个整数A1, A2, ... AN。请你从中选出K个数,使其乘积最大。 请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以1000000009的余数。 注意,如果X, 我们定义X除以...
高精度,是学C语言漫长的路上必须要学的一类程序,菜鸡博主大一刷OJ时候的存货
2、适用人群:主要针对计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、数学、电子信息等)的同学或企业员工下载使用,具有较高的学习借鉴价值。 3、不仅适合小白学习实战练习,也...
URI在线裁判 在2014年和2015年期间,教授教授在“编程语言”和“数据结构”学科中授课。 在[FATEC Sorocaba](fatecsorocaba.edu.br)的Antonio Cesar Munari ,我们向学生们提交了一些练习清单,其中许多都是通过...
许多关于ACM的网站,包括OJ,论坛,AC代码(ZOJ).希望能对大家有所帮助.
南京大学 高级程序设计 2020-2021 ppt+作业(含答案)+oj+大项目
oj题目源代码,用于备份和测试oj题目源代码,用于备份和测试oj题目源代码,用于备份和测试
oj 的c++类与对象之前包括类与对象的全答案
LeetCode作者: 我的LeetCode OJ的C ++代码。请给这个仓库 :star:如果它启发了你。谢谢。 :smiling_face_with_smiling_eyes: :weary_face:解决LeetCode问题时,讨厌讨厌手动复制并粘贴示例测试用例吗? :backhand_...