「BZOJ1263」[SCOI2006] 整数划分
Description
从文件中读入一个正整数n（10≤n≤31000）。要求将n写成若干个正整数之和，并且使这些正整数的乘积最大。 例如，n=13，则当n表示为4+3+3+3（或2+2+3+3+3）时，乘积=108为最大。
Input
只有一个正整数： n （10≤n≤31000）
Output
第1行输出一个整数，为最大乘积的位数。 第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。 （提示：在给定的范围内，最大乘积的位数不超过5000位）。
Sample Input
13
Sample Output
3
108
108
题解
划分尽量多的3直到n<=4为止
然后写个压位高精度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,l=1,d[3000],ans[3000]={1}; int get(int x) { if(x>=1000)return 4; if(x>=100)return 3; if(x>=10)return 2; else return 1; } void cal(int x) { for(int i=0;i<l;i++)ans[i]*=x; for(int i=0;i<l;i++) { ans[i+1]+=ans[i]/10000; ans[i]%=10000; } while(ans[l]>0){ans[l+1]+=ans[l]/10000;ans[l]%=10000;l++;} } int main() { scanf("%d",&n); while(n>4){n-=3;cal(3);}cal(n); for(int i=0;i<l;i++)d[i]=get(ans[i]); printf("%d\n",(l-1)*4+d[l-1]); printf("%d",ans[l-1]); int i; for(i=l-2;i>=max(0,l-25);i--) { for(int j=d[i];j<4;j++)printf("0"); printf("%d",ans[i]); } if(i>=0) { if(d[l-1]==3)printf("%d",ans[i]/1000); else if(d[l-1]==2){if(ans[i]<10)printf("0");printf("%d",ans[i]/100);} else if(d[l-1]==1) { if(ans[i]<100)printf("0"); if(ans[i]<10)printf("0"); printf("%d",ans[i]/10); } } return 0; } |
计数器 9854364
OI 课件=>
OI 课件=>
我爱您黄学长
黄学长快看看~
21741 Qwq