4. 做蛋糕
题目ID：3687100分
最新提交：
Wrong Answer
10 分
历史最高：
Wrong Answer
10 分
时间限制: 2000ms
空间限制: 524288kB
题目描述
小明学做蛋糕，因为事先买好了底盒，所以蛋糕的最下层只能做成面积大小为n，蛋糕可以做成单层，也可以做成多层，上一层的面积不能超过下一层面积的2/3，每层面积都只能是整数，请问小明最多可能做出几种形状的蛋糕。
输入格式
一行一个整数n，表示蛋糕底层面积
输出格式
一个数，表示小明最多可能做出的蛋糕总数
样例
Input 1
4
Output 1
4
样例解释
底面积为4，可以做一层，可以做面积为4,2的两层，4,1的两层，还可以做4,2,1的三层，一共有4种形状的蛋糕。
数据范围
1≤n≤5000
code:
#include<bits/stdc++.h>
using namespace std;
int n,a[5005];
int main(){
a[1]=1;
a[2]=2;
a[3]=4;
cin>>n;
for(int i=4;i<=n;i++){
a[i]+=a[i/3*2]*2;
}
cout<<a[n];
}