Fighting_小银考呀考不过四级
原题地址
这道题卡了我很长时间，主要是没明白规律。
这里借用一下别人的讲法：
我们用 f[n] 表示有n个座位，且至少坐一个人的坐法种类数。
f[n]有两种情况：
1.最后一个位置不坐人，则等价于f[n-1]
2.最后一个位置坐人，则n-1，n-2的位置就不能坐人了，这样等价于f[n-3],但最后一个位置已经坐人了所以前n-3个位置可以不做人，因此总的f[n-3]+1;
原文：https://blog.csdn.net/qq_32426313/article/details/54346610
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
//#include<math.h>
using namespace std;
long long gcd(int n){
long long f[999];
f[1]=1;
f[2]=2;
for(int i=3;i<=n;i++)
f[i] = f[i-3]+f[i-1]+1;
return f[n];
}
int main( )
{
int n,m ;
while(cin >>n){
cout<<gcd(n)<<endl;
}
return 0;
}
查看15道真题和解析
