整数划分区间dp-蒲公英云

整数划分区间dp

怼烎@ 2022-08-20 15:15 381阅读 0赞

题目链接点击打开链接

题目大意是说有一个不超过二十位的数字，要将这个数字划分成n段，最后让这n段数字相乘，问怎么划分使乘积最大。

分析：

一个很经典的区间dp问题，我们可以先保存下这个数字的每段的大小，也就是a[i][j]表示的这个数字的i位到j位的大小。

然后就是一个很普通的区间dp了，dp[i][j]表示的是前i位里面插入j个乘号所得到的最大值。

我们知道最后的乘积肯定比原来的那个数字小，所以没有超过long long的范围。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int const maxn = 21 ;
long long dp[maxn][maxn];
long long Arr[maxn][maxn];
int main()
{
    int t,m ;
    string n;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        cin>>n>>m;
        m--;///m-1个乘号
        int len=n.length();
        for(int i=0;i<len;i++)
        {
            Arr[i][i]=n[i]-'0';
            for(int j=i+1;j<len;j++)
            {
                Arr[i][j]=Arr[i][j-1]*10+n[j]-'0';
            }
        }
        for(int i=0;i<len;i++)
        {
            dp[i][0]=Arr[0][i];
        }
        for(int j=1;j<=m;j++)  //j为*数目
        {
            for(int i=j;i<len;i++)//i为数字位置（肯定要从j开始，要包含*处理完）
            {
                for(int k=j-1;k<i;k++)//枚举区间
                {
                    dp[i][j]=max(dp[i][j],dp[k][j-1]*Arr[k+1][i]);
                }
            }
        }
        printf("%lld\n",dp[len-1][m]);
    }
    return 0;
}