点击打开链接
整数拆段 Description 将一个位数为L的自然数N拆成4段，使各段对应的数的乘积最小。你能编一个程序实现吗？ Input 一个自然数N。 Output 一个整数，最小乘积。 Sample Input 321427 Sample Output 2268 Hint 100%的数据满足：4≤L≤10 思路 直接枚举，分四段 代码示例 #include<bits/stdc++.h> using namespace std; char str[11]; int fun(int s,int e){ int num=0; for(int i=s;i<=e;++i){ num=num*10+str[i]-'0'; } //cout<<str[0]<<endl; return num; } int main() { cin>>str; long long min=100000000000000; //cout<<min<<endl; int len=strlen(str); for(int i=1;i<=len-3;++i) for(int j=i+1;j<=len-2;++j){ for(int k=j+1;k<=len-1;++k){ //cout<<i<<j<<k<<"(⊙o⊙)…"<<endl; //cout<<fun(0,i-1)<<' '<<fun(i,j-1)<<' '<<fun(j,k-1)<<' '<<fun(k,len-1)<<endl; if((fun(0,i-1)*fun(i,j-1)*fun(j,k-1)*fun(k,len-1))<min){ min=fun(0,i-1)*fun(i,j-1)*fun(j,k-1)*fun(k,len-1); } } } cout<<min<<endl; return 0; }
优化
如果数的位数增多，枚举显然力不从心
考虑DP思想，利用f数组记录1到所求位数所有的分拆为1到4的最优值
为什么这样能节省时间呢？
因为长度分拆为j位的最优结果f[i][j]满足
f[i][j]=min(f[i][j],f[k][j-1]*a[k+1][i])其中k<i,a为辅助求值数组
代码示例
#include<bits/stdc++.h> using namespace std; const long long inf=1e11; char s[15]; long long a[15][15]; long long f[15][5];//优质数组 int len; long long get(int x,int y) { long long ans=0; for(int i=x;i<=y;++i) ans=ans*10+(s[i]-'0'); return ans; } int main() { scanf("%s",s+1); s[0]='0'; len=strlen(s)-1; //准备 for(int i=1;i<=len;++i){ for(int j=i;j<=len;++j) a[i][j]=get(i,j); } for(int i=0;i<15;++i) for(int j=0;j<5;++j) f[i][j]=inf; for(int j=0;j<5;++j) f[0][j]=1; for(int i=1;i<=len;++i){ for(int j=1;j<=4;++j){ for(int k=0;k<i;++k){//利用前面的最优值 f[i][j]=min(f[i][j],f[k][j-1]*a[k+1][i]);//a[k+1][i]表示最后一段(k+1到i)的值 } } } printf("%lld\n",f[len][4]); return 0; }