1225: 文科生的悲哀-标准题解（C++代码），26行代码，效率极高，DFS+记忆化搜索

#include <iostream>
using namespace std;
int n,a[4][10001];//a[i][j]用来记录还剩j次考试时且这次考试是第i门时的总情况数。避免深搜的重复计算次数，提高效率。 
int dfs(int step,int sign)
{
	if(a[sign][n-step]!=0)
	{
		return a[sign][n-step];//输出已经得出的该情况下的步数 
	}
	if(step==n-1)
	{
		return 1;//最后一次考试，不需要再往后推了，直接返回1。 
	}
	switch(sign)
	{ 
		case 0:return a[sign][n-step]=(a[sign][n-step]+dfs(step+1,1))%7654321;
		case 1:return a[sign][n-step]=(a[sign][n-step]+dfs(step+1,2)+dfs(step+1,0))%7654321;
		case 2:return a[sign][n-step]=(a[sign][n-step]+dfs(step+1,1)+dfs(step+1,3))%7654321;
		case 3:return a[sign][n-step]=(a[sign][n-step]+dfs(step+1,2))%7654321;
	}
}
int main()
{
	cin>>n;
	cout<<dfs(0,0);
}