观察样例，令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 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11837180.html
