首页 > 代码库 > hdu 5151 Sit sit sit

hdu 5151 Sit sit sit

2024-10-20 19:29:02   213人阅读

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

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

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

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

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define mod 1000000007 5 #define ll long long 6 using namespace std; 7  8 int n; 9 int a[200];10 ll c[200][200];11 ll dp[200][200];12 13 void inti()14 {15     for(int i=0; i<=101; i++)16     {17         c[i][0]=1;18         for(int j=1; j<=i; j++)19         {20             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;21         }22     }23 }24 25 ll get_num(int x,int y)26 {27     if(x>y) return 0;28     if(dp[x][y]) return dp[x][y];29     if(x==y) return dp[x][y]=1;30     ll ans=0;31     for(int i=x+1; i<y; i++)32     {33         if(a[i-1]!=a[i+1]) continue;34         ans+=get_num(x,i-1)*get_num(i+1,y)%mod*c[y-x][i-x]%mod;35         ans%=mod;36     }37     ans+=get_num(x+1,y);38     ans%=mod;39     ans+=get_num(x,y-1);40     ans%=mod;41     dp[x][y]=ans;42     return dp[x][y];43 }44 45 int main()46 {47     inti();48     while(scanf("%d",&n)!=EOF)49     {50         memset(dp,0,sizeof(dp));51         for(int i=1; i<=n; i++)52         {53             scanf("%d",&a[i]);54         }55         printf("%lld\n",get_num(1,n));56     }57     return 0;58 }
View Code

 

hdu 5151 Sit sit sit


联系
我们