1 solutions
Information
- ID
- 704
- Time
- 1000ms
- Memory
- 16MiB
- Difficulty
- 9
- Tags
- # Submissions
- 10
- Accepted
- 8
- Uploaded By
考虑最后一次的放置方法,当我们的n大于3的时候,最后一次无非就三种,放1、放2、放3,那么也就是说我们的f[n]是从f[n−1] 、f[n−2] 、f[n−3] 转移过来的也就说f[n]=f[n−1]+f[n−2]+f[n−3],这样就能处理大于3的情况了,对于小于等于3的情况我们直接手动计算即可
#include<iostream>
using namespace std;
int main()
{
int n;
long long f[55]={0,1,2,4};
cin>>n;
for(int i = 4;i <= n; ++i) f[i] = f[i-1] + f[i-2] + f[i-3];
cout<<f[n]<<endl;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.