menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】DP——整数划分
2020-05-16 | 【OI】 | 暂无评论 | 55 次阅读 | 285字

    上个星期终于到机房里去上课了。今天好好做题,加油!整数划分这道题还是比较水的,算是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++码风。
    好,本题的记录就到这里,我们下一题见。

None
发表评论
暂无评论
textsms
account_circle
email
link