SDUT3146：Integer division 2（整数划分区间dp)

题目描述

This is a very simple problem, just like previous one.

You are given a postive integer n, and you need to divide this integer into m pieces. Then multiply the m pieces together. There are many way to do this. But shadow95 want to know the maximum result you can get.

输入

First line is a postive integer t, means there are T test cases.

Following T lines, each line there are two integer n, m. (0<=n<=10^18, 0 < m < log10(n))

输出

Output the maximum result you can get.

示例输入

1

123 2

示例输出

提示

You can divide "123" to "12" and "3".

Then the maximum result is 12*3=36.

题意很简单，但是我就是个渣渣，dp的题在比赛里从来没有A过，果断还是看了题解，也只是会了这个类型，其他类型的区间dp果断还是不会，果断不能举一反三啊。

代码如下：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

typedef long long ll;

using namespace std;

#define mod 1000000007

int m,l;

char s[];//局部变量与全局变量求字符串长度完全不同

ll a[][],dp[][];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s+);

        scanf("%d",&m);

        l=strlen(s+);

        memset(a,,sizeof(a));

        if(m==||m==)

        {

            printf("%s\n",s+);

            continue;

        }

        for(int i=;i<=l;i++)

        {

            for(int j=i;j<=l;j++)

            {

                a[i][j]=a[i][j-]*+(s[j]-'');

            }

        }

        memset(dp,,sizeof(dp));

        for(int i=;i<=l;i++)

            dp[i][]=a[][i];

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

        {

            for(int i=j;i<=l;i++)

            {

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

                {

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

                }

            }

        }

        printf("%lld\n",dp[l][m]);

    }

    return ;

}

巴特西

SDUT3146：Integer division 2（整数划分区间dp)

题目描述

输入

输出

示例输入

示例输出

提示

最新文章

热门文章