Luogu P1018 乘积最大

gate

就这个破题dp+高精度...我de了好久/kk

设f[i][j]表示前i个数，用了j个*号，num(l,r)表示从第l位到第r位表示的数字

f[i][j] = max(f[i][j],f[k][j-1]*num(k+1,i))

不用高精是60pts，代码如下：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

#define int long long

int n,q,a[50],f[50][50];

int num(int l,int r) {
    int ret = 0;
    for(int i = l; i <= r; i++) {
        ret *= 10;
        ret += a[i];
    }
    return ret;
}

main() {
    scanf("%lld%lld",&n,&q);
    for(int i = 1; i <= n; i++)
        scanf("%1lld",&a[i]);
    for(int i = 1; i <= n; i++)
        f[i][0] = num(1,i);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= q; j++)
            for(int k = 1; k <= i-1; k++)
                f[i][j] = max(f[i][j],f[k][j-1]*num(k+1,i));
    printf("%lld",f[n][q]);
}

View Code

然后我居然是把字符串先转成int再转成高精...我真傻 真的

写了直接转高精之后，判断前导0没写边界，死循环了，又RE...

100分代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

struct HAI {
    static const int Mx = 50;
    int num[Mx],len;

    HAI() {
        clean();
    }

    void clean() {
        memset(num,0,sizeof(num));
        len = 1;
    }

    void write() {
        for(int i = len; i >= 1; i--)
            printf("%d",num[i]);
    }

    HAI operator * (const HAI &A) const {
        HAI S;
        S.len = len + A.len - 1;
        for(int i = 1; i <= len; i++)
            for(int j = 1; j <= A.len; j++) {
                int k = i+j-1;
                S.num[k] += num[i] * A.num[j];
                S.num[k+1] += S.num[k] / 10;
                S.num[k] %= 10;
            }
        while(S.num[S.len+1]) S.len++;
        while(!S.num[S.len] && S.len > 1) S.len--;
        return S;
    }

    bool operator < (const HAI &A) const {
        if(len != A.len) return len < A.len;
        for(int i = len; i >= 1; i--)
            if(num[i] != A.num[i])
                return num[i] < A.num[i];
        return false;
    }

} f[50][50],N;

int n,q,a[50];

HAI getnum(int l,int r) {
    HAI N;
    N.clean();
    int k = l;
    while(!a[k] && k < r) k++;
    for(int i = r;i >= k;i--)
        N.num[N.len++] = a[i];
    if(N.len > 1) N.len--;
    return N;
}

int main() {
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++)
        scanf("%1d",&a[i]);
    for(int i = 1; i <= n; i++)
        f[i][0] = getnum(1,i);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= q; j++)
            for(int k = 1; k <= i-1; k++) {
                N = getnum(k+1,i);
                f[i][j] = max(f[i][j],f[k][j-1] * N);
            }
    f[n][q].write();
    return 0;
}

View Code