2018年蓝桥杯C/C++B组国赛-激光样式

题目

题目链接

题解

动态规划，或者找规律。

找规律的话是斐波那契数列。

动态规划的话也很简单，dp[i][0/1]表示前i个灯，第i个灯开或不开的方案数，转移方程为dp[i][0] = dp[i-1][0] + dp[i-1][1]、dp[i][1] = dp[i-1][0]，最后输出dp[30][0] + dp[30][1]。

代码

#include
using namespace std;

int dp[40][2]; // dp[i][0/1] 表示开第i台的方案数与不开第i台的方案数  

int main()
{
	int n = 30;
	dp[1][1] = dp[1][0] = 1;
	for (int i = 2;i