昨天晚上去菜鸟启航他们宿舍玩儿的时候，看见他在做这道题。当时我也没看题目，就看见他声明了一个叫DP的数组。我当时特激动，我就问他会不会做，不会做的话尽管问我，我一定会不吝赐教的。结果他直接把我轰出来了。。。。
一道挺水的DP，我甚至觉得都不算DP，就是一个跟那个红色病毒一样的递归，一个三维多态的递归。dp[i][j][k]中j和k分别表示项链的前两颗钻石的状态，加入一个新的钻石的状态可以由之前两个状态推出来。
[cpp] #include
#include
#define N 10000
#define M 9997
int dp[N][2][2];
int main()
{
int n,i;
while(scanf("%d",&n),n!=-1)
{
memset(dp,0,sizeof(dp));
dp[1][0][1]=1;
dp[1][0][0]=1;
for(i=2;i<=n;i++)
{
dp[i][0][1]=dp[i-1][0][0]%M;
dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%M;
dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%M;
dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%M;
}
int sum;
sum=dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1];
printf("%d\n",sum%M);
}
return 0;
}
#include
#include
#define N 10000
#define M 9997
int dp[N][2][2];
int main()
{
int n,i;
while(scanf("%d",&n),n!=-1)
{
memset(dp,0,sizeof(dp));
dp[1][0][1]=1;
dp[1][0][0]=1;
for(i=2;i<=n;i++)
{
dp[i][0][1]=dp[i-1][0][0]%M;
dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%M;
dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%M;
dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%M;
}
int sum;
sum=dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1];
printf("%d\n",sum%M);
}
return 0;
}