划分DP 将一个n位数划分为m部分使得各部分乘积最大

#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
using namespace std;
int n,m;
long long a[210][210];        //a[i][j] 表示从i到j位的这个数
long long dp[210][210];       //dp[i][j] 表示从前i位中划分出j次的最大乘积
long long x;
void Init()
{
    long long tem = x;
    for(int i = n; i>= 1; i--)
    {
        a[i][i] = tem%10;
        tem/=10;
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = i-1; j >= 1; j--)
        {
            a[j][i] = a[j][i-1]*10+a[i][i];
        }
    }
    for(int i = 1; i <= n; i++)
        dp[i][0] = a[1][i];
}
int main()
{
    scanf("%d%d",&n,&m);
    cin>>x;
    Init();
    //一共划分为m+1个部分
    for(int i = 2; i <= n; i++)             //前n个数
    {
        for(int j = 1; j <= m && j < i; j++)      //划分j次
        {
            for(int k = 1; k < i; k++)            //前k个数划分j-1份，从 k加1 个数到i为第j份
            {
                dp[i][j] = max(dp[i][j], dp[k][j-1]*a[k + 1][i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}