40pts求调
查看原帖
40pts求调
1263684
Elysialr楼主2024/11/5 19:57
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m;
string dp[100][100][10];
string s;

string cheng(string a,string b){
    string res;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    
    for(ll i=1;i<=(a.size()+b.size());i++)
    res+='0';
    for(ll i=0;i<a.size();i++)
    for(ll j=0;j<b.size();j++){
        ll x=a[i]-'0',y=b[j]-'0';
        ll z=x*y;
        res[i+j]+=z;
        if(res[i+j]>'9'){
            res[i+j+1]+=(res[i+j]-'0')/10;
            res[i+j]=(res[i+j]-'0')%10+'0';
        }
    }
    while(res.back()=='0')
    res.pop_back();
    reverse(res.begin(),res.end());
    return res;
}

string num(ll l,ll r){
    string res="";
    bool sw=true;
    for(ll i=l;i<=r;i++){
        if(sw&&s[i]=='0')
        continue;
        sw=false;
        res+=s[i];
    }
    
    return res;
}

string max_str(string a,string b){
    if(b.size()<a.size()) return a;
    if(a.size()<b.size()) return b;
    for(ll i=0;i<a.size();i++){
        if(b[i]<a[i]) return a;
        if(a[i]<b[i]) return b;
    }
    return a;
}

int main(){
    cin>>n>>m;
    cin>>s;
    s=" "+s;
    for(ll len=1;len<=n;len++)
    for(ll i=1,j=len;j<=n;i++,j++){
        dp[i][j][0]=num(i,j);
        for(ll c=1;c<=min(len-1,m);c++)
        for(ll k=i+c-1;k<j;k++)
        dp[i][j][c]=max_str(dp[i][j][c],cheng(dp[i][k][c-1],num(k+1,j)));
    }

    cout<<dp[1][n][m];
    return 0;
}
2024/11/5 19:57
加载中...