0分求助
查看原帖
0分求助
350446
chenxuanzhen楼主2020/8/18 10:15
#include<bits/stdc++.h>
using namespace std;
int n, k;
const int N = 110;
char S[N];
struct bigNumber{
    int len, x[110];
    bigNumber(){len=1;}
    void pint(){
        for(int i = len; i; i--) printf("%d",x[i]);
        puts("");
    }
} f[N][N],s[N][N];
bigNumber fix(bigNumber a){
    for(int i = 1; i < a.len; ++i){
        a.x[i+1] += a.x[i] / 10;
        a.x[i] %= 10;
    }
    while(a.x[a.len] >= 10){
        a.x[a.len+1] += a.x[a.len]/10;
        a.x[a.len] %= 10;
        a.len++;
    }
    while(!a.x[a.len] && a.len > 1) a.len--;
    return a;
}
inline bigNumber operator *(bigNumber a, int b){
    for(int i = 1; i <= a.len; ++i) a.x[i] *= b;
    return fix(a);
}
inline bigNumber operator *(bigNumber a, bigNumber b){
    bigNumber c;
    for(int i = 0; i < 110; ++i) c.x[i] = 0;
    c.len = a.len + b.len - 1;
    for(int i = 1; i <= a.len; ++i)
        for(int j = 1; j < b.len; ++j)
            c.x[i+j-1] += a.x[i] * b.x[j];
    return fix(c);
}
inline bigNumber operator + (bigNumber a, int b){
    a.x[1] += b;
    return fix(a);
}
inline bool operator <(bigNumber a, bigNumber b){
    if(a.len != b.len) return a.len < b.len;
    for(int i = a.len; i; --i)
        if(a.x[i] != b.x[i]) return a.x[i] < b.x[i];
    return 0;
}
int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",S + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            s[i][j] = s[i][j-1] * 10 + (S[j]-'0');
    for(int i = 1; i <= n; ++i){
        f[i][0] = s[1][i];
        for(int j = 1; j <= k; ++j)
            for(int d = j; d < i; ++d)
                f[i][j] = max(f[i][j],f[d][j-1]*s[d+1][i]);
    }
    f[n][k].pint();
    return 0;
}
2020/8/18 10:15
加载中...