XTU OJ 1175 学习笔记

#include
using namespace std;
 
typedef long long LL;
const int N=50;
LL a[N][5];
 
void initialize()
{
	a[1][1]=a[1][2]=a[1][3]=a[1][4]=1;
	for(int i=2;i<=45;i++)
	{
		a[i][1]=a[i-1][2]+a[i-1][3];
		a[i][2]=a[i-1][1]+a[i-1][3]+a[i-1][4];
		a[i][3]=a[i-1][1]+a[i-1][2]+a[i-1][4];
		a[i][4]=a[i-1][2]+a[i-1][3];
	}
}
 
int main()
{
	initialize();
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		LL ans=0;
		ans=a[n][1]+a[n][2]+a[n][3]+a[n][4];
		//printf("%I64d\n",ans);
		cout<
	}
	return 0;
}

参考题解： 

1.题解1

2.题解2

根据题意，1旁边只能是2/3，2旁边只能是1/3/4，3旁边只能是1/2/4，4旁边只能是2/3，首先看一下数据范围，2或者3的45次方，2^45/3^45，这个超过了2^31，超过了int的数据范围，所以我们需要使用long long

我们使用一个数组来存储数字。第一个位置可以存1/2/3/4，有四种情况，假设第一个位置存的是1/4，那么第二个位置就只能存2/3，只有两种情况，假设第一个位置存的是2/3，第二个位置有三个数字可以选择。那么我们到底应该怎么考虑这个问题？

（笔者也是初学者，所以如有错误欢迎大佬指正）动态规划（dp）来解决这道题， 动态规划最关键的就是建立状态转移方程。

动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

状态转移方程就是这个，

    a[1][1]=a[1][2]=a[1][3]=a[1][4]=1;
	for(int i=2;i<=45;i++)
	{
		a[i][1]=a[i-1][2]+a[i-1][3];
		a[i][2]=a[i-1][1]+a[i-1][3]+a[i-1][4];
		a[i][3]=a[i-1][1]+a[i-1][2]+a[i-1][4];
		a[i][4]=a[i-1][2]+a[i-1][3];
	}

从第一个元素开始处理，每一次循环，前面的数据是已经被处理过的数据（被计算过），这一点和前缀和的思路有点儿类似。循环结束，所有元素都被处理过了。

输出64位整数，使用%I64d