首页分享洛谷 P1018 乘积最大

洛谷 P1018 乘积最大

来源：花匠小妙招时间：2024-12-09 10:14

传送门：洛谷 P1018 乘积最大
算法分析：
首先，算法主体为区间DP，设 (f[i][j]) 为在中分i个乘号的最大结果
则 (f[i][j]=max{f[i][j],f[i-1][t]times a[t+1][j]})
其中 (iin[1,k]) , (jin[i+1,n]) , (tin[i,j)) , (a) 中存储所有拆分数

考虑到本题的数据量，使用高精度乘法计算
高精度乘法实现：
分为5个函数：

remix ：将数组中的数右对齐 give ：将数组中的内容拷贝到另一个数组中 write ：去前导0并输出 comp ：比较函数 multi ：进行竖式运算

#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef unsigned long long ull; const int maxN=100; struct Node { int num[maxN+1]; }; int n,k,a[maxN+1],b[maxN+1],c[maxN+1]; char s[maxN+1]; Node dp[maxN+1][maxN+1]; ull a1[maxN+1][maxN+1]; void remix(int[],ull),reset(),DP(); void multi(int[],int[]); void give(int[],int[]),write(); int comp(int[],int[]); int main() { reset(); DP(); write(); return 0; } void remix(int a[],ull num) { int len=0,lent=0; ull temp=num; while(num) {lent++; num/=10;} len=lent; while(temp) {a[--lent]=temp%10; temp/=10;} for(int i=maxN;i>=0;i--,len--) if(len>0) a[i]=a[len-1]; else a[i]=0; } void reset() { scanf("%d%d%s",&n,&k,s); memset(a1,0,sizeof(a1)); for(int i=0;i<n;i++) for(int j=i;j<n;j++) a1[i+1][j+1]=a1[i+1][j]*10+s[j]-'0'; for(int i=0;i<=n;i++) remix(dp[0][i].num,a1[1][i]); } void DP() { for(int i=1;i<=k;i++) for(int j=i+1;j<=n;j++) { memset(dp[i][j].num,0,sizeof(dp[i][j].num)); for(int t=i;t<j;t++) { memset(c,0,sizeof(c)); int now[maxN+1]={0}; remix(now,a1[t+1][j]); multi(dp[i-1][t].num,now); if(comp(dp[i][j].num,c)==-1) give(dp[i][j].num,c); } } } void write() { int i=0; while(i<maxN && dp[k][n].num[i]==0) i++; while(i<=maxN) printf("%d",dp[k][n].num[i++]); } void multi(int a[],int b[]) { int jw,t; for(int i=maxN;i>maxN/2;i--) { jw=0; t=i; for(int j=maxN;j>maxN/2;j--) { c[t]+=a[i]*b[j]+jw; jw=c[t]/10; c[t--]%=10; } c[t--]=jw; } } int comp(int a[],int b[]) { int len1=0,len2=0; while(a[len1]==0) len1++; while(b[len2]==0) len2++; if(len1<len2) return 1; if(len1>len2) return -1; for(;len1<=maxN;len1++) { if(a[len1]<b[len1]) return -1; if(a[len1]>b[len1]) return 1; } return 0; } void give(int change[],int own[]) { for(int i=0;i<=maxN;i++) change[i]=own[i]; }