nyoj-746

整数划分（四）

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

暑假来了，hrdv 又要留学校在参加ACM集训了，集训的生活非常Happy nyoj-746 （ps：你懂得），可是他最近遇到了一个难题，让他百思不得其解，他非常郁闷。。亲爱的你能帮帮他吗？

问题是我们经常见到的整数划分，给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积

输入

第一行是一个整数T，表示有T组测试数据
接下来T行，每行有两个正整数 n，m ( 1<= n < 10^19, 0 < m <= n的位数)；

输出

输出每组测试样例结果为一个整数占一行

样例输入

样例输出

11

121

来源

经典题目

上传者

TC_胡仁东

区间dp。

开始我被样例忽悠了，以为所有的整数都是1111....这种形式的，后来才知道并不是。

根据区间dp的思想，我们定义dp [ i ] [ j ]为从开始到 i 中加入 j 个乘号得到的最大值。

那么我们可以依次计算加入1----m-1个乘号的结果

而每次放入x个乘号的最大值只需枚举第x个乘号的放的位置即可

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

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

#define ll long long

#define repu(i, a, b) for(int i = a; i < b; i++)

#define repd(i, a, b) for(int i = b; i >= a; i--)

#define sfi(n) scanf("%d", &n)

#define pfi(n) printf("%d\n", n)

#define _cle(m, a) memset(m, a, sizeof(m))

ll a[][];

ll dp[][];

char s[];

int n, k;

void init()

{

    _cle(a, );

    repu(i, , n) repu(j, i, n) repu(k, i, j + )

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

}

int main()

{

    int T;

    sfi(T);

    while(T--)

    {

        _cle(dp, );

        scanf("%s", s);

        n = strlen(s);

        init();

        sfi(k); k--;

        repu(i, , n + )

        {

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

            repu(j, , k + ) repu(p, , i)

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

        }

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

    }

    return ;

}

整数划分（四）

相关文章