为备战蓝桥杯，我每天把刷题经验总结成博客，鞭策自己学习，争取暑假输出三十篇以上。

本篇是一题动态规划的题目及题解。

题目链接

题目链接


题解

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int res[1000005];
int temp[1000005];
int main(){
	int n;
	cin>>n;
	res[1]=1;
	res[2]=2;
	temp[2]=1;
	for(int i=3;i<=n;i++){
		res[i]=(res[i-1]+res[i-2]+2*temp[i-1])%10000;
		temp[i]=(res[i-2]+temp[i-1])%10000;
	}
	cout<<res[n];
	return 0;
}