P1018 乘积最大(DP)
程序员文章站
2023-11-04 12:40:52
题目 "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$为当前区间长度 ......
题目
解析
区间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])