[bzoj1263]整数划分

观察样例，令f(n)表示n拆分的答案，猜想$f(n)=3f(n-3)$，当$n\le 4$时$f(n)=n$
取3的原因是因为对于给定的$x+y$，当$4<x+y$，显然有$3^{x+y-3}$最大，否则直接取$x+y$即为最大值，也就是给出的递推式

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define P 10

 4 int n,ans[10005];

 5 void cheng(int k){

 6     ans[1]*=k;

 7     for(int i=2;i<=ans[0];i++){

 8         ans[i]=ans[i]*k+ans[i-1]/P;

 9         ans[i-1]%=P;

10     }

11     if (ans[ans[0]]>=P){

12         ans[ans[0]+1]=ans[ans[0]]/P;

13         ans[ans[0]++]%=P;

14     }

15 }

16 int main(){

17     scanf("%d",&n);

18     ans[0]=ans[1]=1;

19     while (n>4){

20         n-=3;

21         cheng(3);

22     }

23     cheng(n);

24     printf("%d\n",ans[0]);

25     for(int i=ans[0];i>max(ans[0]-100,0);i--)printf("%d",ans[i]);

26 }

巴特西

[bzoj1263]整数划分

最新文章

热门文章