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][][]);
}