P1018 乘积最大(DP)

时间：2023-03-09 06:50:36
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])

相关文章