动态规划学习系列——划分DP（一）

划分型DP，是解决跟划分有关的题目的一种DP思路，个人觉得，是目前接触的DP类型中最难的一种，因为感觉思路并不确定，不过正是不确定，才可以体会到算法的精妙之处。

题目链接：wikioi_1017
要求是将一个n位的数分成m部分，使各部分的乘积最大。解题的思路基于一个事实：当前的数可以分成m-1部分，那么加多几位分成m部分不是可以从原来的推出来。从这句差不多是废话的话中我们就可以推出状态转移方程：
dp[i][k]=max(dp[i][k],dp[j][k-1]*a[j+1][i]); ( k <= j < i )
dp[i][k]表示将从1~i位分成k+1部分的最大乘积。（用[1 , i]而不用[i , j]是避免了重复的计算）
于是，主代码可得出：

for(int k=1;k<=m;k++)
    for(int i=k+1;i<=n;i++)
        for(int j=k;j<i;j++)
            dp[i][k]=max(dp[i][k],dp[j][k-1]*a[j+1][i]);

当然，预处理是少不了的：

long long tmp=num;              //num为输入的数
for(int i=n;i>=1;i--){          //获得数的每一位
    a[i][i]=tmp%10;
    tmp/=10;
}

for(int i=2;i<=n;i++)           //a[i][j]表示从i~j的这个数
    for(int j=i-1;j>=1;j--)
        a[j][i]=a[j][i-1]*10+a[i][i];

for(int i=1;i<=n;i++)           //初始化dp数组
    dp[i][0]=a[1][i];

完整代码：

#include <bits/stdc++.h>

using namespace std;

int n,m;
long long num,a[45][45],dp[45][45];

int main()
{
    scanf("%d %d",&n,&m);
    scanf("%lld",&num);

    long long tmp=num;
    for(int i=n;i>=1;i--)
    {
        a[i][i]=tmp%10;
        tmp/=10;
    }

    for(int i=2;i<=n;i++)
        for(int j=i-1;j>=1;j--)
            a[j][i]=a[j][i-1]*10+a[i][i];

    for(int i=1;i<=n;i++)
        dp[i][0]=a[1][i];
    for(int k=1;k<=m;k++)
    {
        for(int i=k+1;i<=n;i++)
        {
            for(int j=k;j<i;j++)
            {
                dp[i][k]=max(dp[i][k],dp[j][k-1]*a[j+1][i]);
            }
        }
    }
    printf("%lld\n",dp[n][m]);

    return 0;
}

总结：
作为一道划分型DP的题，很不错的一道题。原本题意是划分，但通过DP的手段，看起来已经不再是划分了，而是有点像添加，可见算法之美啊！
因为这道题是2000年的题，题目比较老，所以数据量比较小，用long long就可以过了，不需要高精度，dp+高精度的话就是一道比较难的题了，主要是没有高精度的模版（跪求高精度模板QAQ）