欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P1018 乘积最大(DP)

程序员文章站 2022-06-09 14:12:40
题目 "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$为当前区间长度 ......

题目

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