BZOJ 4321 queue2

4321: queue2

Description

n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行；现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。

Input

只有一行且为用空格隔开的一个正整数 N，其中 100%的数据满足 1≤N ≤ 1000;

Output

一个非负整数，表示方案数对 7777777 取模。

Sample Input

Sample Output

2
样例解释：有两种方案 2 4 1 3 和 3 1 4 2

　　这道题还真没想到是DP。

　　去年NOIP考前看到此题，当时竟不知DP，只会暴力。至此便叹息痛恨焉。

　　昨夜又见，虽欣喜，然不知何为。

　　直到我看见：【bzoj4321】queue2

　　啊啊啊啊啊！这篇博客已经讲得很详细了。这n个沙茶可以一个一个插入。

　　状态表示：f[i][j][0..1]=前i个沙茶有j对是相邻的，其中第i个沙茶和第i-1个沙茶相不相邻

　　初始状态：f[1][0][0]=1

　　状态转移：

　　f[i][j][1]<-f[i-1][j][1] 第i个沙茶插在了第i-1个和第i-2个之间

<-f[i-1][j-1][1] 第i个沙茶插在了第i-1个旁边，第i-2个的另一侧

<-f[i-1][j-1][0]*2 第i个沙茶插在了第i-1个的左右两侧（第i-1个不与第i-2个相邻）

　　f[i][j][0]<-f[i-1][j+1][1]*j 第i个沙茶落了单，干坏事。可以拆散j对，因为不能拆散第i-1个和第i-2个

<-f[i-1][j+1][0]*(j+1) 第i个沙茶落了单，干坏事。可以拆散j+1对

<-f[i-1][j][1]*(i-j-1) 第i个沙茶落了单，兀自玩去了。(i-1+1)-(j+1)，不能拆散j对也不能在第i-1个旁边

<-f[i-1][j][0]*(i-j-2) 第i个沙茶落了单，兀自玩去了。(i-1+1)-(j+2)，不能拆散j对也不能在第i-1个旁边

　　答案输出：ans=f[n][0][0]

　　可用滚动数组。时间O(n^2)，空间O(n)。

　　不过还有递推式：http://oeis.org/A002464 f[n]=(n+1)f[n−1]−(n−2)f[n−2]−(n−5)f[n−3]+(n−3)f[n−4]

　　此题转移中分类讨论很有意思，是一道很好的题。注意不要爆int。

 /**************************************************************

     Problem: 4321

     User: Doggu

     Language: C++

     Result: Accepted

     Time:484 ms

     Memory:852 kb

 ****************************************************************/

 #include <cstdio>

 long long n, f[][][], cur, MOD=;

 inline void add(long long &a,long long b) {if(b>MOD) b%=MOD;a=a+b>MOD?a+b-MOD:a+b;}

 int main() {

     scanf("%d",&n);

     f[cur][][]=;

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

         cur^=;

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

             f[cur][j][]=f[cur^][j][];

             if(j) add(f[cur][j][],f[cur^][j-][]);

             if(j) add(f[cur][j][],f[cur^][j-][]*);

             f[cur][j][]=f[cur^][j+][]*j;

             add(f[cur][j][],f[cur^][j+][]*(j+));

             add(f[cur][j][],f[cur^][j][]*(i-j-));

             add(f[cur][j][],f[cur^][j][]*(i-j-));

         }

     }

     printf("%d\n",f[cur][][]);

     return ;

 }

巴特西