HDU 4532 추수 시리즈 스토리-좌석 배치(DP)

제목 링크
시합할 때 생각이 없어요.문제풀이를 보고 나니 이해하기 어렵다.지난번 CF에 나왔던 그룹 DP, 다 비슷한 느낌이었죠...
pp[i][j]는 전 i조에 j개가 서로 인접해 있고 좌우가 같은 계의 위치임을 나타낸다.
현재 a[i]개인에 대해 말하자면 k조로 나눌 수 있고 u를 열거할 수 있다. 만약에 이 k조에 u조가 j개의 위치에 있다면.이때 연결된 것은 j-u+a[i]-k로 변한다.
각종 조합을 곱하다.

 1 #include <cstdio>

 2 #include <cstring>

 3 using namespace std;

 4 #define MOD 1000000007

 5 #define LL __int64

 6 LL c[501][501];

 7 int a[501];

 8 LL dp[51][501];

 9 LL fact[51];

10 int Min(int a,int b)

11 {

12     return a < b ? a:b;

13 }

14 int main()

15 {

16     int i,j,k,u,n,t,cas = 1,sum,minz;

17     for(i = 0;i <= 500;i ++)

18     {

19         c[i][0] = 1;

20     }

21     for(i = 1;i <= 500;i ++)

22     {

23         for(j = 1;j <= 500;j ++)

24         c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;

25     }

26     fact[0] = 1;

27     for(i = 1;i <= 50;i ++)

28     {

29         fact[i] = (fact[i-1] * i)%MOD;

30     }

31     scanf("%d",&t);

32     while(cas <= t)

33     {

34         scanf("%d",&n);

35         memset(dp,0,sizeof(dp));

36         sum = 0;

37         for(i = 1;i <= n;i ++)

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

39         dp[1][a[1]-1] = 1;

40         sum = a[1];

41         for(i = 2;i <= n;i ++)

42         {

43             for(j = 0;j < sum;j ++)

44             {

45                 minz = Min(a[i],sum+1);

46                 for(k = 1;k <= minz;k ++)

47                 {

48                     for(u = 0;u <= j&&u <= k;u ++)

49                     {

50                         dp[i][j-u+a[i]-k] = (dp[i][j-u+a[i]-k]+(((((dp[i-1][j]*c[j][u])%MOD)*c[sum+1-j][k-u])%MOD)*c[a[i]-1][k-1]))%MOD;

51                     }

52                 }

53             }

54             sum += a[i];

55         }

56         LL ans = dp[n][0];

57         for(i = 1;i <= n;i ++)

58         {

59             ans = (ans*fact[a[i]])%MOD;

60         }

61         printf("Case %d: %I64d
",cas,ans);

62         cas ++;

63     }

64     return 0;

65 }