洛谷P1018 乘积最大两种做法

目前整理了两种做法

方法一：

设a为输入的字符串，num【i】【j】表示字符串中从下标为i到j（故从0开始）的一串数字。那么可以得到

for(int i=0;i<n;i++)  num[ i ][ i ]=a[ i ]-'0';
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
num[i][j]=num[i][j-1]*10+a[j]-'0';

这是一个递推，第一行是设置边界，递推关系式即num[i][j]=num[i][j-1]*10+a[j]-'0';

设f【i】【j】表示在0到i间加入i个乘号的最大乘积，则状态转移方程为：

for(int k=1;k<=x;k++)
for(int i=k;i<n;i++)//注意i从0开始
for(int j=k-1;j<i;j++)
f[k][i]=max(f[k][i],f[k-1][j]*num[j+1][i]);

边界设置如下：

for(int i=0;i<n;i++）
f[0][i]=num[0][i];代码如下，但这样只有60分，AC需要使用高精度乘法，下次再加上

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=41;
char a[N];
int x,n,len;
long long f[N][N],num[N][N];
int main()
{
    //freopen("in.txt","r",stdin);
    cin>>n>>x;
    cin>>a;
    for(int i=0;i<n;i++) num[i][i]=a[i]-'0';
    for(int i=0;i<n;i++)
       for(int j=i+1;j<n;j++)
        num[i][j]=num[i][j-1]*10+a[j]-'0';
        
    for(int i=0;i<n;i++)
    f[0][i]=num[0][i];  
    for(int k=1;k<=x;k++)
      for(int i=k;i<n;i++)//注意i从0开始 
        for(int j=k-1;j<i;j++)
        f[k][i]=max(f[k][i],f[k-1][j]*num[j+1][i]);
    cout<<f[x][n-1];/**/
    
    return 0;
}
方法二：

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,maxx;
int a[41];
char ch;
void dfs(int x,int ans,int last)
{
    if(x==k)
    {
    int mul=0;
    for(int j=last+1;j<n;j++)
    {mul+=a[j];
    mul*=10;}
    mul+=a[n];
    maxx=max(maxx,ans*mul);
    return;
    }
    for(int i=last+1;i<=n-k+x;i++)
    {
        int mul=0;
        for(int j=last+1;j<i;j++)
        {mul+=a[j];
        mul*=10;}
        mul+=a[i];
        dfs(x+1,ans*mul,i);
    }
}
int main()
{
	freopen("in.txt","r",stdin);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        a[i]=ch-'0';
    }
    dfs(0,1,0);//初始值处理   
    cout<<maxx;
}

　　这种做法来自sumyt，原文：

题解 P1018 【乘积最大】 - sunyt 的博客 - 洛谷博客
https://www.luogu.org/blog/user17407/solution-p1018

void dfs（三个已插入的乘号个数，当前乘积，上一个插入的乘号的位置）中

第三个形参的说明：比如在1231中插了一个变成：1*231，那么该形参表示的是“*”左边的1的位置

for(int j=last+1;j<i;j++)
{
mul+=a[j];
mul*=10;
}
mul+=a[i]; 
mul表示上一乘号到刚插入的这个乘号之间的数字。
好啦解释（ban yun）完毕。