2803 爱丽丝·玛格特罗依德

 

 时间限制: 4 s

 空间限制: 8000 KB

 题目等级 : 黄金 Gold

 查看运行结果

 

 

题目描述 

Description

在幻想乡中，爱丽丝·玛格特罗依德是一名居住在魔法森林的魔法使，擅长 

召唤人偶。一天她的“机油”帕秋莉找到了她，要他防御雾雨魔理沙对巴瓦卢魔 

法图书馆的“破坏”。

她有n点魔法值，每召唤出一个『上海人形』就要消耗若干点（x），最后， 

它们造成的威力就是每个人形所消耗的魔法值的总积。

她为了知道能有多少威力，找到了全幻想乡唯一会编程的你，你不会让她 

失望吧？

 

Rewrote From Izayoi Sakuya

输入描述 

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

分类标签 Tags 

 

 

题解：

小学奥数……？ 

多拆出3 要不就是2 

听题解说是这样的 

顺带一提，高精度（+压位）

AC代码：

#include
     
      #include
      
       int n,a[2000];inline void mul(int t){    int j=0;    for(int i=1;i<=a[0]+1;i++){        a[i]=a[i]*t+j;        j=0;        if(a[i]>=100000000){            j=a[i]/100000000;            a[i]=a[i]%100000000;        }    }    if(a[a[0]+1]>0) a[0]++;}inline void zero(int p){    for(int q=8-log10(p);q;q--) printf("0");}int main(){    scanf("%d",&n);    if(n<=4) printf("%d",n);    else{        a[1]=3;        a[0]=1;        if(n%3==0) for(int k=n/3-1;k>0;k--) mul(3);        if(n%3==1){            for(int k=(n-4)/3-1;k>0;k--) mul(3);            mul(2);            mul(2);        }        if(n%3==2){            for(int k=(n-2)/3-1;k>0;k--) mul(3);            mul(2);        }        printf("%d",a[a[0]]);        for(int k=a[0]-1;k>=1;k--){            zero(a[k]);            printf("%d",a[k]);        }    }    return 0;}