1 solutions

  • 1
    @ 2022-3-1 12:38:56

    思路

    考虑最后一次的放置方法,当我们的n大于3的时候,最后一次无非就三种,放1、放2、放3,那么也就是说我们的f[n]f[n]是从f[n1]f[n-1]f[n2]f[n-2]f[n3]f[n-3] 转移过来的也就说f[n]=f[n1]+f[n2]+f[n3]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;
    }
    
    • 1

    Information

    ID
    704
    Time
    1000ms
    Memory
    16MiB
    Difficulty
    9
    Tags
    # Submissions
    10
    Accepted
    8
    Uploaded By