洛谷P1018乘积最大——区间DP

题目：https://www.luogu.org/problemnew/show/P1018

区间DP+高精，注意初始化和转移的细节。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 20005

using namespace std;

typedef long long ll;

ll n,k,a[],f[][][MAXN],tmp[MAXN],num[MAXN];

char dc[];

void nm(ll l,ll r)

{

//    printf("l=%lld r=%lld\n",l,r);

    num[]=r-l+;

    for(ll i=l;i<=r;i++)//正存即可

        num[i-l+]=a[i];

//    for(int i=1;i<=num[0];i++)printf("%lld",num[i]);

//    cout<<endl;

}

void init()

{

    a[]=strlen(dc);

    for(ll i=;i<=a[];i++)

    {

        a[i]=dc[a[]-i]-'';

//        memset(num,0,sizeof num);

//        nm(1,i);

        memcpy(f[i][],f[i-][],sizeof f[i-][]);//注意初始化！

        f[i][][]++;f[i][][i]=a[i];

    }

}

void ch(ll a[],ll b[])

{

    tmp[]=a[]+b[]-;

    for(ll i=;i<=a[];i++)

        for(ll j=;j<=b[];j++)

        {

            tmp[i+j-]+=a[i]*b[j];

            tmp[i+j]+=tmp[i+j-]/;

            tmp[i+j-]%=;

        }

    if(tmp[tmp[]+])tmp[]++;

}

bool com(ll a[],ll b[])

{

    if(a[]>b[])return ;

    if(a[]<b[])return ;

    for(ll i=a[];i;i--)

    {

        if(a[i]>b[i])return ;

        if(a[i]<b[i])return ;

    }

    return ;

}

void print(ll a[])

{

    for(ll i=a[];i;i--)

        printf("%lld",a[i]);

}

int main()

{

    scanf("%lld%lld",&n,&k);

    cin>>dc;

    init();

//    f[1][1][0]=1;f[1][1][1]=1;

    for(ll i=;i<=n;i++)

        for(ll l=;l<=min(i-,k);l++)

            for(ll j=l;j<i;j++)//从l开始!!!

            {

//                f[i][l]=max(f[j][l-1]*num(j+1,i),f[i][l]);

                memset(tmp,,sizeof tmp);

                memset(num,,sizeof num);

                nm(j+,i);

                ch(f[j][l-],num);

                if(com(tmp,f[i][l]))memcpy(f[i][l],tmp,sizeof tmp);

            }

    print(f[n][k]);

    return ;

}