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])