整数划分区间dp

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

题目链接[点击打开链接][Link 1]

题目大意是说有一个不超过二十位的数字，要将这个数字划分成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;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/status.php?pid=746