hdu 5151 Sit sit sit

http://acm.hdu.edu.cn/showproblem.php?pid=5151

题意：一共有N个椅子，然后有N个学生依次去坐，满足下面三个条件不能坐上去，1：这个椅子旁边有左椅子也有右椅子，2：椅子旁边都有人坐了，3：椅子旁边的椅子颜色不一样。

问如果所有人都坐上去有多少情况。

dp[i][j] 表示区间[i,j]满足的情况数。 这道题是一道区间dp。把一个很大的区间化成多个很小的区间处理。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define mod 1000000007

 #define ll long long

 using namespace std;

 int n;

 int a[];

 ll c[][];

 ll dp[][];

 void inti()

 {

     for(int i=; i<=; i++)

     {

         c[i][]=;

         for(int j=; j<=i; j++)

         {

             c[i][j]=(c[i-][j]+c[i-][j-])%mod;

         }

     }

 }

 ll get_num(int x,int y)

 {

     if(x>y) return ;

     if(dp[x][y]) return dp[x][y];

     if(x==y) return dp[x][y]=;

     ll ans=;

     for(int i=x+; i<y; i++)

     {

         if(a[i-]!=a[i+]) continue;

         ans+=get_num(x,i-)*get_num(i+,y)%mod*c[y-x][i-x]%mod;

         ans%=mod;

     }

     ans+=get_num(x+,y);

     ans%=mod;

     ans+=get_num(x,y-);

     ans%=mod;

     dp[x][y]=ans;

     return dp[x][y];

 }

 int main()

 {

     inti();

     while(scanf("%d",&n)!=EOF)

     {

         memset(dp,,sizeof(dp));

         for(int i=; i<=n; i++)

         {

             scanf("%d",&a[i]);

         }

         printf("%lld\n",get_num(,n));

     }

     return ;

 }