牛客假日团队赛9 A 乘积最大 (简单DP)

题目：https://ac.nowcoder.com/acm/contest/1071/A

题意：给你一个串，然后给你m个乘号，用m个乘号分割开这个串，然后求分割可以求出的最大值

思路：首先范围很小

第一种：我把所有乘号分隔最多只有 C(40,6) 种方案，很少，我们直接dfs就可以算出来

第二种：dp做法，我们考虑数组 dp[n][m]

n代表当前位置，m代表用了m个乘号，然后数组值是到当前位置用m个乘号的最大值

我们考虑最后一段数是在哪里，我们枚举位置，然后算出最后一段的值*前面位置用m-1个乘号的最大值

转移方程：dp[i][j]=max(dp[i][j],dp[k][j-1]*最后一段数值)

#include<bits/stdc++.h>

#define maxn 1100

#define mod 1000000007

using namespace std;

typedef long long ll;

ll dp[][],n,m;

char str[maxn];

int main(){

    cin>>n>>m;

    cin>>str+;

    for(int i=;i<=n;i++){

        ll dex=,sum=;

        while(dex<=i){

            sum=sum*+str[dex]-'';

            dex++;

        }

        dp[i][]=sum;

        for(int j=;j<=m;j++){

            for(int k=;k<=i-;k++){

                ll dex=k+,sum=;

                while(dex<=i){

                    sum=sum*+str[dex]-'';

                    dex++;

                }

                dp[i][j]=max(dp[i][j],dp[k][j-]*sum);

            }

        }

    }

    cout<<dp[n][m];

    return ;

}

巴特西

牛客假日团队赛9 A 乘积最大 (简单DP)

最新文章

热门文章