【dp】最大乘积
2024-08-28 17:27:48
题目描述】
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:312, 当N=3,K=1时会有以下两种分法:
1)3*12=36
2)31*2=62
这时,符合题目要求的结果是:31*2=62。
现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
【输入】
第一行共有2个自然数N,K(6≤N≤10,1≤K≤6)
第二行是一个长度为N的数字串。
【输出】
输出所求得的最大乘积(一个自然数)。
【输入样例】
4 2
1231
【输出样例】
62
【思路】:
设f[i][k]表示在前i位数中插入K个乘号所得的最大值,a[j][i]表示从第j位到第i位所组成的自然数。用f[i][k]存储阶段K的每一个状态,
f[i][k]=max{f[j][k-1]*a[j+1][i]}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
char c = getchar();
int x = , f = ;
while(c < '' || c > '') {
if(c == '-') f = -;
c = getchar();
}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
long long int n,k,a[][],f[][];
int main() {
cin>>n>>k;
long long int t;
cin>>t;
for(int i=n; i>=; --i) {
a[i][i]=t%;
t/=;
}
/* 拆分数*/
for(int i=; i<=n; ++i) {
for(int j=i-; j>=; --j) {
a[j][i]=a[j][i-]*+a[i][i];
//a[i][j]表示从i到j位的数
}
}
/*for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
cout<<a[i][j]<<" ";
}
cout<<"\n";
}*/
for(int i=; i<=n; ++i) { //初始化成不带*的情况
f[i][]=a[][i];
}
for(int t=; t<=k; ++t) { //枚举乘号
for(int i=t+; i<=n; ++i) {
for(int j=t; j<i; ++j) {
f[i][t]=max(f[i][t],f[j][t-]*a[j+][i]);
/*前i位中插入t个x号就是前j位插入t-1个x号在*后面的所有数*/
}
}
}
cout<<f[n][k];
return ;
}
最新文章
- [Unity3D入门]分享一个自制的入门级游戏项目";坦克狙击手";
- gtest
- NoSuchMethodError: antlr.collections.AST.getLine()I
- [leetCode][012] Two Sum (1)
- CSS笔记(十五)CSS3之用户界面
- 如何用JS判断网页中某个id的网页元素是否存在
- python学习札记(1)
- 卓尼斯ZT-180评測
- 彻底解决 LINK : fatal error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏
- atom编辑器快捷键
- Visual Studio 与 Matlab实现混合编程
- install.php文件建表时设置编码方式
- C语言的第一次作业总结
- jQuery在页面加载的时候自动调用某个函数的方法
- linux - man 提示:No entry for tty in section 4 of the manual
- 优化 Markdown 在 Notepad++ 中的使用体验
- maven依赖和传递
- python中和生成器协程相关的yield from之最详最强解释,一看就懂(四)
- 001.网络TCP/IP工程知识点
- JS replace()用法实现replaceAll