bzoj 4321: queue2 （DP）

題目描述

傳送門

題目大意：求1-n的排列中，滿足每個數的左右兩邊的數與自己相差都不是1的方案數。

題解

剛開始排列組合亂搞，無果。。。。受到點啟發後開始想DP，不過還是想了很久。

f(i,j,0) 表示從1..i順序插入序列，有j對相鄰的數相差1，第i個數與第i-1個數不相鄰。

f(i,j,1) 表示從1..i順序插入序列，有j對相鄰的數相差1，第i個數與第i-1個數相鄰。

然後考慮插入第i個數對之前序列的影響。

f(i,j,0)=f(i−1,j,0)∗(i−j−2)+f(i−1,j,1)∗(i−j−1)+f(i−1,j+1,0)∗(j+1)+f(i−1,j+1,1)∗j

f(i−1,j,0)∗(i−j−2) 表示不破壞相鄰的每一對，那麼這j對中間的位置不能選，同時還不能與i-1相鄰，因為i-1不和i-2相鄰，是以不再j對中，他左右的位置都不能選。

f(i−1,j,1)∗(i−j−1) 表示不破壞相鄰的每一對，i-1,i-2相鄰是以i-1隻有一邊的位置需要放棄。

f(i−1,j+1,0)∗(j+1) 表示破壞了相鄰的其中一對

f(i−1,j+1,1)∗j 不能插入到i-1,i-2之間，否則會形成新的一對相鄰的。

f(i,j,1)=f(i−1,j−1,0)∗2+f(i−1,j,1)+f(i−1,j−1,1)

f(i−1,j−1,0)∗2 i-1,i-2不相鄰，加入到i-1的任意一邊都會産生新的一對

f(i−1,j,1) 加入到i-1,i-2中間，對數不變

f(i−1,j−1,1) 加入到i-1不與i-2相鄰的一邊，對數+1.

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1003
#define p 7777777
#define LL long long 
using namespace std;
int n;
LL f[N][N][];
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d",&n);
    memset(f,,sizeof(f));
    f[][][]=;
    for (int i=;i<=n;i++)
     for (int j=;j<=n;j++) {
        f[i][j][]=f[i-][j][]*(LL)(i-j-)+f[i-][j][]*(LL)(i-j-);
        f[i][j][]%=p;
        f[i][j][]+=f[i-][j+][]*(LL)(j+)+f[i-][j+][]*(LL)j;
        f[i][j][]%=p;
        f[i][j][]=f[i-][j][];
        if (j) f[i][j][]+=f[i-][j-][]*+f[i-][j-][];
        f[i][j][]%=p;
     }
    printf("%lld\n",f[n][][]);
}