信息学奥赛一本通 1275：【例9.19】乘积最大

ybt 1275：【例9.19】乘积最大
原题为：信息学奥赛一本通 1912：【00NOIP普及组】乘积最大
原题中N最大为40，必须用高精度数字来做。该题中N最大为10，可以用long long类型来做。

在一个最多10位数中，插入最多6个乘号，有最多7个数字相乘。
将拆分出的每个数字都扩大为大于等于它的最小的10的幂（两位数及100变为100，三位数及1000变为1000，x位数及 1 0 x 10^x 10x变为 1 0 x 10^x 10x），乘积结果为 1 0 n 10^n 10n，n为原数字的位数，n最大为10，所以结果最大为 1 0 10 10^{10} 1010，可以用long long表示。

预先处理，num[i][j]表示该数字从第i位到第j位截取出的数字。
将输入的数字m进行数字拆分，存在数组a中。双重循环，双指针倒序遍历a数组，i指向最高位，j指向最低位，用数字正向组合的写法，将这些位数字组合起来，求出第i到第j位的数字。

集合：在数字中插入乘号的方案
限制：看前几位数字，使用几个乘号
属性：乘积
条件：最大
统计量：乘积
状态定义：dp[i][j]：在前i位数字中插入j个乘号能得到的最大乘积。
初始状态：dp[i][0]：前i位数字中插入0个乘号，乘积就是这i位数字。dp[i][0] = num[1][i]

集合：在前i位数字中插入j个乘号的方案
分割集合：根据第j个乘号插入位置的不同情况分割集合
因为第j个乘号前面还有j-1个乘号，最密集插入乘号，每两个乘号间有1位数字，第j-1个乘号会在第j-1位数字的后面。第j个乘号可能的最靠前的位置，为第j位数字的后面。
第j个乘号可以取到的最靠后的位置，为第i-1位数字的后面。
假设第j个乘号在第h位数字的后面，那么第j乘号后面的数字，为第h+1位到第i位组成的数字。
h从j遍历到i-1，先求出前h位数字中插入j-1个乘号能得到的最大乘积(dp[h][j-1])，再乘以第h+1位到第i位组成的数字(num[h+1][i])，得到前i位数字插入j个乘号的最大乘积：dp[i][j] = dp[h][j-1]*num[h+1][i]。对所有可能的情况取最大值。

本题将一段数字分为前半段（前h位数字插入j-1个乘号）与后半段（数字num[h+1][i]），类似于区间动规中遍历断点，将一个大区间拆分为小区间的思想。

#include
using namespace std;
#define N 20
long long dp[N][N], num[N][N], m;//dp[i][j]：在前i位数字中插入j个乘号能得到的最大乘积。
int n, k;
void initNum()
{
    int a[N], ai = 0; 
    for(long long i = m; i > 0; i /= 10)//注意，这里可能保存m的数字都要设为long long 
        a[++ai] = i%10;//a:从低位到高位存储m的各个数位
    for(int i = 1; i <= ai/2; ++i)//将a倒序，从高位到低位存储m的各个数位 
        swap(a[i], a[ai-i+1]);
    for(int i = 1; i <= ai; ++i)
    {
        long long x = 0;//构造的数字 
        for(int j = i; j <= ai; ++j)
        {
            x = x*10+a[j];
            num[i][j] = x;//num[i][j]:表示数字m截取第i位到第j位得到的数字 
        }
    }
}
int main()
{
    cin >> n >> k >> m;//m为数字串
    initNum();//初始化num数组
    for(int i = 1; i <= n; ++i)//初始状态 
        dp[i][0] = num[1][i];//前i位数字中插入0个乘号，乘积就是这i位数字
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= k; ++j)
            for(int h = j-1; h < i; ++h)
                dp[i][j] = max(dp[i][j], dp[h][j-1]*num[h+1][i]);
    cout << dp[n][k];
	return 0;
}