学步园

点击打开链接

题意:

有一个跳舞毯，其中有A,B,C三个区域，开始从A，结束为A，求跳n次的种类数。

两种思路：

1

当第i-1次在A时，有dp[i-1]，所以第i-1不再A的情况也是dp[i-1]（因为i-2次可能在B，可能在C，如果在B，跳到C，在C，跳到B)

当i-2次在A时，dp[i-2]*2

dp[i]=dp[i-1]+2*dp[i-2];

2

A[0]=1;B[0]=C[0]=0;

A[i]=B[i-1]+C[i-1];

B[i]=A[i-1]+C[i-1];

C[i]=A[i-1]+B[i-1];

很简单，都算出来就可以了

#include"stdio.h"
#include"string.h"
#define N 1101

int A[N];
int B[N];
int C[N];

int main()
{
	int n;
	int i;
	A[0]=1;
	B[0]=0;
	C[0]=0;
	for(i=1;i<=1000;i++)
	{
		A[i]=B[i-1]+C[i-1];
		B[i]=A[i-1]+C[i-1];
		C[i]=A[i-1]+B[i-1];
		A[i]%=10000;
		B[i]%=10000;
		C[i]%=10000;
	}
	while(scanf("%d",&n)!=-1,n)
		printf("%d\n",A[n]);
	return 0;
}

#include"stdio.h"
#include"string.h"
#define N 1101

int dp[N];
int main()
{
    int n;
    int i;
    dp[1]=0;
    dp[2]=2;
    for(i=3;i<=1000;i++)
    {
        dp[i]=dp[i-1]+dp[i-2]*2;
        dp[i]%=10000;
    }
    while(scanf("%d",&n)!=-1,n)
        printf("%d\n",dp[n]);
    return 0;
}