3 solutions

  • 0
    @ 2022-4-7 20:09:29

    不太会的dfs算法 QAQ

    #include<iostream>
    
    using namespace  std;
    bool light[35];
    long long ans;
    
    void  dfs(int n)
    {
    	if (n == 31)//边界判断
    	{
    		ans++;
    		return;
    	}
    	if (light[n - 1]) dfs(n + 1);
    	//前灯亮则此灯不亮,进入下一层搜索
    	else {//前灯不亮
    		light[n] = true;//标记
    		dfs(n + 1);//此灯亮
    		light[n] = false;//重新标记
    		dfs(n + 1);//此灯不亮
    	}
    
    }
    int main(void)
    {
    	int sum = 30;
    	dfs(1);
    	cout << ans;
    
    	return 0;
    }
    • 0
      @ 2022-4-4 22:22:02
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      //通过列出前5项,找到规律,这是一个斐波那契数列
      //数据范围小,不需要记搜,直接递推就完了
      ll fib(int x){
          if(x==1)return 2;
          if(x==2)return 3;
          return fib(x-1)+fib(x-2);
      }
      int main(){
        cout<<fib(30);
        return 0;
      }
      
      • 0
        @ 2022-2-20 21:48:25

        动态规划题

        #include <bits/stdc++.h>
        using namespace std;
        long long dp[2][38];
        int main(){
        	dp[0][1]=1,dp[1][1]=1;
        	for(int i=2;i<=30;i++){
        		dp[0][i]=dp[0][i-1]+dp[1][i-1];
        		dp[1][i]=dp[0][i-1];
        	}
        	cout<<dp[0][30]+dp[1][30];
        	return 0;
        }
        • 1

        Information

        ID
        52
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        4
        Tags
        # Submissions
        29
        Accepted
        17
        Uploaded By