[NOIP 2000 提高组] 乘积最大

知识点

划分动态规划、高精度、字符串转整数

解题思路

预处理每个连续子串对应的大整数。f[i][j]表示前i位插入j个乘号的最大乘积，枚举最后一段起点，转移为前段最优乘积乘最后一段。用自实现高精度支持40位输入。

正确性说明

任意分法最后一个乘号将串划分为已分好的前缀与最后一段。枚举其位置覆盖所有分法；因最后一段非负，使用前缀最大乘积不会变差。按段数归纳得最优结果。大整数运算逐位进位，保持精确值。

易错点

必须恰用K个乘号，每段非空；前导0对应整数0；40位结果可能超过128位。

复杂度

O(KN²)次大整数运算，最长40位；空间O(N²)个大整数。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Big{static const int B=10000;vector<int>d;Big(long long x=0){do{d.push_back(x%B);x/=B;}while(x);}void trim(){while(d.size()>1&&d.back()==0)d.pop_back();}bool operator<(const Big&o)const{if(d.size()!=o.d.size())return d.size()<o.d.size();for(int i=(int)d.size()-1;i>=0;i--)if(d[i]!=o.d[i])return d[i]<o.d[i];return false;}Big operator+(const Big&o)const{Big r;r.d.assign(max(d.size(),o.d.size())+1,0);int carry=0;for(int i=0;i<(int)r.d.size();i++){int v=carry+(i<(int)d.size()?d[i]:0)+(i<(int)o.d.size()?o.d[i]:0);r.d[i]=v%B;carry=v/B;}r.trim();return r;}Big operator*(const Big&o)const{vector<long long>v(d.size()+o.d.size()+1);for(int i=0;i<(int)d.size();i++)for(int j=0;j<(int)o.d.size();j++)v[i+j]+=1LL*d[i]*o.d[j];Big r;r.d.resize(v.size());for(int i=0;i<(int)v.size();i++){if(i+1<(int)v.size())v[i+1]+=v[i]/B;r.d[i]=v[i]%B;}r.trim();return r;}Big operator*(int x)const{return *this*Big(x);}Big operator/(int x)const{Big r=*this;long long rem=0;for(int i=(int)d.size()-1;i>=0;i--){long long v=rem*B+d[i];r.d[i]=v/x;rem=v%x;}r.trim();return r;}friend ostream&operator<<(ostream&os,const Big&a){os<<a.d.back();for(int i=(int)a.d.size()-2;i>=0;i--)os<<setw(4)<<setfill('0')<<a.d[i];return os;}};

int main(){int n,k;string s;cin>>n>>k>>s;vector<vector<Big>>val(n,vector<Big>(n));for(int l=0;l<n;l++){Big x;for(int r=l;r<n;r++){x=x*10+Big(s[r]-'0');val[l][r]=x;}}vector<vector<Big>>f(n+1,vector<Big>(k+1));for(int i=1;i<=n;i++)f[i][0]=val[0][i-1];for(int j=1;j<=k;j++)for(int i=j+1;i<=n;i++)for(int t=j;t<i;t++){Big cur=f[t][j-1]*val[t][i-1];if(f[i][j]<cur)f[i][j]=cur;}cout<<f[n][k]<<'\n';}