hdu 3485（水DP)

昨天晚上去菜鳥啟航他們宿捨玩兒的時候，看見他在做這道題。當時我也沒看題目，就看見他聲明了一個叫DP的數組。我當時特激動，我就問他會不會做，不會做的話盡管問我，我一定會不吝賜教的。結果他直接把我轟出來了。。。。

一道挺水的DP，我甚至覺得都不算DP，就是一個跟那個紅色病毒一樣的遞歸，一個三維多態的遞歸。dp[i][j][k]中j和k分別表示項鏈的前兩顆鑽石的狀態，加入一個新的鑽石的狀態可以由之前兩個狀態推出來。

[cpp]  #include<stdio.h>  
#include<string.h>  
#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<stdio.h>
#include<string.h>
#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;
}