洛谷1018 乘积最大

就是一道区间dp+高精，最开始还想拿int_128来水水的，结果算算还是不太够，就老老实实写了高精。

$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值，转移方程式为：

$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$

每次转移时枚举放乘号的位置 $(mid)$ 和左右两边的乘号个数 $(x$ 和 $cnt-x-1)$ 即可。

因为我很菜，所以还是写的记搜。

struct bigint{
    int s[45],len;
    bigint(){memset(s,0,sizeof(s));len=0;}
} f[45][45][7];

bigint times(bigint x,bigint y)
{
    bigint z;
    int lx=x.len,ly=y.len;
    for (int i=1;i<=lx;i++)
    {
        int add=0;
        for (int j=1;j<=ly;j++)
        {
            int now=x.s[i]*y.s[j]+add;
            z.s[i+j-1]+=now%10;
            if (z.s[i+j-1]>=10) z.s[i+j-1]-=10,z.s[i+j]++;
            add=now/10;
        }
        if (add) z.s[i+ly]+=add;
    }
    z.len=lx+ly;
    while (!z.s[z.len]) z.len--;
    return z;
}

inline int cmp(bigint x,bigint y)
{
    if (x.len>y.len) return 1;
    if (x.len<y.len) return -1;
    for (int i=x.len;i;i--)
    {
        if (x.s[i]<y.s[i]) return -1;
        if (x.s[i]>y.s[i]) return 1;
    }
    return 0;
}

inline void print(bigint x)
{
    for (int i=x.len;i;i--)
        printf("%d",x.s[i]);
}

int n,m,a,b,c,s[45];

bigint dfs(int st,int ed,int cnt)
{
    if (f[st][ed][cnt].s[1]) return f[st][ed][cnt];
    bigint &ans=f[st][ed][cnt],now;
    for (int i=0;i<cnt;i++)
    {
        for (int j=st;j<ed;j++)
        {
            now=times(dfs(st,j,i),dfs(j+1,ed,cnt-i-1));
            if (cmp(now,ans)==1) //now>ans,ans=now
            {
                for (int k=1;k<=now.len;k++) ans.s[k]=now.s[k];
                ans.len=now.len;
            }
        }
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    char ch[45];
    scanf("%s",ch);
    for (int i=0;i<n;i++)
        s[n-i]=ch[i]-'0';
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            for (int k=i;k<=j;k++)
                f[i][j][0].s[++f[i][j][0].len]=s[k];
    print(dfs(1,n,m));
    return 0;
}