牛客假日团队赛10 L 乘积最大（动态规划）

   首先看一下题意：有一串数字，要求在这串数字中加入k个乘号，使得乘积最大。比如在1231中加入两个乘号，最大的就是。这个题是一道比较基础的动态规划题目，下面说一下我自己的理解。

   我们令dp[i][j]表示前i个数中加入j个乘号的最大值，用num[n][m]表示这串数中从n到m的数值，可以提前预处理下。这里我们让乘号递增，让乘号作为最外层循环。那么我们可以得到状态转移方程:，其中k从j开始，一直加到len-1（字符串长度），因为我们每次多加入一个乘号，就意味着要多一个数字，这个数字必然包括最后一个数字，也就是说这个数字的结尾是确定的，就是i，而开头不确定，所以遍历所有可能的开头位置，找出最大的即可。下面贴一下代码，自己最初用long long挂了，后来用了unsigned long long才过。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main(){
    ll n,k;
    ll num[45][45];
    ll dp[45][10];
    cin>>n>>k;
    string t;
    cin>>t;
    ll len=t.length();
    memset(dp,0,sizeof(dp));
    for(int q=0;q<len;q++){
        ll tmp=0;
        for(int w=q;w<len;w++){
            tmp=tmp*10+(t[w]-'0');
            num[q][w]=tmp;
        }
    }
    for(int q=0;q<len;q++){
        dp[q][0]=num[0][q];
    }
    for(int q=1;q<=k;q++){
        for(int w=q;w<len;w++){
            for(int l=q-1;l<len;l++){
                dp[w][q]=max(dp[w][q],dp[l][q-1]*num[l+1][w]);
            }
        }
    }
    cout<<dp[len-1][k];
    return 0;
}