codevs 2803 爱丽丝·玛格特罗依德

爱丽丝·玛格特罗依德"/>

codevs 2803 爱丽丝·玛格特罗依德

codevs 2803 爱丽丝·玛格特罗依德

题目描述

在幻想乡中，爱丽丝·玛格特罗依德是一名居住在魔法森林的魔法使，擅长 召唤人偶。一天她的“机油”帕秋莉找到了她，要他防御雾雨魔理沙对巴瓦卢魔 法图书馆的“破坏”。她有n点魔法值，每召唤出一个『上海人形』就要消耗若干点（x），最后， 它们造成的威力就是每个人形所消耗的魔法值的总积。
她为了知道能有多少威力，找到了全幻想乡唯一会编程的你，你不会让她 失望吧？

输入描述 Input Description
n

输出描述 Output Description
最大威力

样例输入 Sample Input
10

样例输出 Sample Output
36

数据范围及提示 Data Size & Hint
0< n<10^5

10=2+2+3+3 36=2*2*3*3

思路：尽可能多拆出3来，3拆不出来了就用2。10^5个3相乘长度不超过16000，暴力单精乘勉强可以过。

附上弱弱的代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a[100000];
void cf(int x)//暴力单精乘
{for(int i=1;i<=16000;i++){a[i]*=x;}for(int i=1;i<=16000;i++){a[i+1]+=a[i]/10;a[i]%=10;}
}
int main()
{int n;scanf("%d",&n);if(n<=4)//n在4以下不用管它{printf("%d",n);return 0;}a[1]=1;if(n%3==0){for(int i=n/3;i>=1;i--){cf(3);}}if(n%3==1){for(int i=n/3-1;i>=1;i--){cf(3);}cf(2);cf(2);}if(n%3==2){for(int i=n/3;i>=1;i--){cf(3);}cf(2);}int l=16000;while(l>1&&!a[l]){l--;}for(int i=l;i>=1;i--){printf("%d",a[i]);}return 0;
}

转载于:.html