P1018 乘积最大(DP)
2019-08-16 07:48:51来源:博客园 阅读 ()
P1018 乘积最大(DP)
题目
P1018 乘积最大
解析
区间DP
设\(f[i][j]\)表示选\(i\)个数,插入\(j\)个乘号时的最大值
设\(num[i][j]\)是\(s[i,j]\)里的数字
转移方程就是\(f[i][k] = max(f[i][k], f[j][k - 1] * num[j + 1][i])\)
\(i\)为当前区间长度,\(j\)为枚举的断点的位置
代码
无高精板
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100;
int n, k;
int f[N][N], num[N][N];
char s[N];
template<class T>inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
x = f ? -x : x;
return;
}
signed main() {
read(n), read(k);
cin >> (s + 1);
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
num[i][j] = num[i][j - 1] * 10 + s[j] - '0';
for (int i = 1; i <= n; ++i) f[i][0] = num[1][i];
for (int l = 1; l <= k; ++l) //插入k个乘号
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
f[i][l] = max(f[i][l], f[j][l - 1] * num[j + 1][i]);
cout << f[n][k];
}
高精
f = [[0 for i in range(50)] for j in range(50)]
num = [[0 for i in range(50)] for j in range(50)]
n, k = map(int, input().split())
s = input()
for i in range(1, n + 1) :
for j in range(i, n + 1) :
num[i][j] = num[i][j - 1] * 10 + int(str(s)[j - 1])
for i in range(1, n + 1) :
f[i][0] = num[1][i]
for l in range(1, k + 1) :
for i in range(1, n + 1) :
for j in range(1, i) :
f[i][l] = max(f[i][l], f[j][l - 1] * num[j + 1][i])
print(f[n][k])
原文链接:https://www.cnblogs.com/lykkk/p/11182204.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:luogu1368 工艺
- 动态规划:最大子串和 2020-01-30
- 最小割最大流定理&残量网络的性质 2019-12-17
- 剑指offer64:滑动窗口的最大值 2019-08-31
- Qt无边框窗体-最大化时支持拖拽还原 2019-08-27
- 【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/ 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash