Contest3298 - [C3]-周五晚上第六节课-递归2

2024-10-25 18:00:00
3333-10-25 22:00:00
ACM排行榜 OI排行榜 提交记录
运行中 公开 当前时间:2024-11-14 12:28:31
题目编号 标题
A【基础】买汽水 吴梓轩(82Byte+ 3ms)
B【基础】土地分割 张铭航(44Byte+ 3ms)
C【入门】统计每个月兔子的总数 王阳明(72Byte+ 3ms)
D斐波那契数列 潘津灏(89Byte+ 4ms)
E【入门】ackman函数 张铭航(117Byte+ 3ms)
F【基础】递归函数(reduce) 刘超荣(ง •̀_•́)ง(252Byte+ 3ms)
G【递归入门】炸弹安放 林祺威(171Byte+ 3ms)
H【入门】汉诺塔的移动次数 林宸辉(43Byte+ 3ms)

信息与公告

#include<bits/stdc++.h>
using namespace std;
int f[1011][3];
int dfs(int x, int cnt){
	if(x == 1){
		if(cnt == 1 || cnt == 0) return 1;
		else return 0;		
	}
	if(f[x][cnt] == 0){
		if(cnt == 0){
			if(f[x - 1][0] == 0) f[x - 1][0] = dfs(x - 1, 0);
			if(f[x - 1][1] == 0) f[x - 1][1] = dfs(x - 1, 1);
			if(f[x - 1][2] == 0) f[x - 1][2] = dfs(x - 1, 2);
			f[x][cnt] = f[x - 1][0] + f[x - 1][1] + f[x - 1][2];
		} else if(cnt == 1){
			if(f[x - 1][0] == 0) f[x - 1][0] = dfs(x - 1, 0);
			f[x][cnt] = f[x - 1][0];
		} else {
			if(f[x - 1][1] == 0) f[x - 1][1] = dfs(x - 1, 1);
			f[x][cnt] = f[x - 1][1];
		}
		f[x][cnt] %= 55555;
	}
	return f[x][cnt];
	
}
int main(){
	int n; cin >> n;
	cout << dfs(n+1,0);
	return 0;
}