上个星期终于到机房里去上课了。今天好好做题，加油！整数划分这道题还是比较水的，算是DP高阶中的入门。题目如下：

给出一个长度为n的数
要在其中加m-1个乘号，分成m段
这m段的乘积之和最大
m < n ≤ 20
有T组数据，T ≤ 10000

    首先，这道题的数据量非常大，所以预处理是必不可少的。那么要预处理什么东西呢？没错，就是任意一段的乘积。

//我们用pls[i][j]来表示从第i个数到第j个数的乘积。代码如下。
for (int i=1;i<=l;i++)
    {
        pls[i][i]=s[i];
        for (int j=i+1;j<=l;j++)
            pls[i][j]=pls[i][j-1]*s[j];
    }

    预处理完成之后就到主体部分了——DP。要想做DP，转移方程必不可少。这道题的转移方程就比较简单了，只有两层。

//我们用f[i][j]来表示从1->i中分j段的最大乘积，那么转移方程就是
f[i][j]=max(f[i][j],f[k][j-1]*pls[k+1][i])。
//其中i的范围是1->n，j的范围是1->min(i,m)
//k来选择这j个分段中最后一个分段的分界点，所以k的范围是1->i-1。

    所以，完整的代码就是这样的：

#include <bits/stdc++.h>
#define MAXN 25
using namespace std;
int m;
int f[MAXN][MAXN];
int s[MAXN];
long long pls[MAXN][MAXN];
int l;
void input()
{
    char tmp[25];
    scanf("%s\n",tmp);
    scanf("%d",&m);
    l=strlen(tmp);
    for (int i=0;i<l;i++)
        s[i+1]=tmp[i]-'0';
    for (int i=1;i<=l;i++)
    {
        pls[i][i]=s[i];
        for (int j=i+1;j<=l;j++)
            pls[i][j]=pls[i][j-1]*s[j];
    }
}
void solve()
{
    for (int i=1;i<=l;i++)
        for (int j=1;j<=min(m,i);j++)
            for (int k=1;k<i;k++)
                f[i][j]=max(f[i][j],f[k,j-1]*pls[k+1][i]);
}
int main()
{
    int t;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        memset(f,0,sizeof(f));
        memset(s,0,sizeof(s));
        input();
        solve();
        cout<<f[l][m]<<endl;
    }
}

    这里插一句话，大爱sublime text的c++码风。
    好，本题的记录就到这里，我们下一题见。