BZOJ4321 queue2

目录

BZOJ4321 queue2题解ｃｏｄｅ

BZOJ4321 queue2

题目传送门

题解

有点麻烦的\(Dp\)。首先我们记\(Dp[i][j][0...1]\)表示枚举到第\(i\)个傻叉沙茶的时候,一共有\(j\)对个沙茶是不合法，并且第\(i\)个沙茶与第\(i-1\)个沙茶是否相邻。然后我们开始分析转移状态： 先从第\(i\)个沙茶与第\(i-1\)个相邻的情况\(f[i][j][1]\)开始讨论。首先我们现在要插入第\(i\)个沙茶，并且它是和第\(i-1\)个沙茶相邻的。如果第\(i-1\)个沙茶与第\(i-2\)是相邻的，那么插入第\(i\)个沙茶之后可能会导致多一对不合法的（插在第\(i-1\)个沙茶右边），或者是仍然与之前一样都是\(j\)对（插在第\(i-1\)个沙茶左边），这样转移过来的状态分别为\(f[i-1][j][1]\)和\(f[i-1][j-1][1]\)。如果第\(i-1\)个沙茶与第\(i-2\)个沙茶不相邻，那么插入第\(i\)个沙茶之后，只会让不合法的对数增加，转移过来的状态为\(f[i-1][j-1][0]\)，并且一共有两种插法（插在\(i\)的左边和右边），所以还要乘以２。总结下来，\(f[i][j][1]\)的转移如下：

\(f[i][j][1]=f[i-1][j][1]+f[i-1][j-1][1]+f[i-1][j-1][0]*2\)

然后我们考虑第\(i\)个沙茶与第\(i-1\)个沙茶不相邻的情况\(f[i][j][0]\)。如果第\(i-1\)个沙茶与\(i-2\)个沙茶相邻的时候，那么插入第\(i\)个沙茶可能会使之前的某一对不合法的状态分开，转移过来的状态为\(f[i-1][j+1][1]\)，或者不会分开不合法的状态，转移过来的状态为\(f[i-1][j][1]\)，并且由于规定了第\(i\)个沙茶与第\(i-1\)个沙茶不能相邻，所以两种转移的方法分别有\(j\)和\(i-j-1\)种。接下来考虑第\(i-1\)个沙茶与第\(i-2\)个沙茶不相邻的时候，那么同样的，分为是否会分开之前不合法的状态，则转移过来的状态分别为\(f[i-1][j+1][0]\)和\(f[i-1][j][0]\)，而两种转移的方法也分别为\(j+1\)和\(i-j-2\)种。总结下来，\(f[i][j][0]\)的转移如下：

\(f[i][j][0]=f[i-1][j+1][1]*j+f[i-1][j][1]*(i-j-1)+f[i-1][j+1][0]*(j+1)+f[i-1][j][0]*(i-j-2)\)

然后就是普通的\(Dp\)了。顺带提一句，不知道为什么，这东西竟然在oeis上有。。然后公式是这样的：

\(f_n=(n+1)f_{n−1}−(n−2)f_{n−2}−(n−5)f_{n−3}+(n−3)f_{n−4}\)

听说可能是容斥。。毫无头绪。

ｃｏｄｅ

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int maxn=1005; const int Md=7777777; int n; ll f[maxn][maxn][2]; /*==================Define Area================*/ void Update(ll &x,ll y) { x+=y;x%=Md; } int main() { read(n); f[1][0][0]=1; for(int i=2;i<=n;i++) { for(int j=0;j<i;j++) { f[i][j][1]=f[i-1][j][1]; if(j) Update(f[i][j][1],f[i-1][j-1][0]*2ll+f[i-1][j-1][1]); Update(f[i][j][0],(ll)f[i-1][j+1][1]*j); Update(f[i][j][0],(ll)f[i-1][j+1][0]*(j+1)); Update(f[i][j][0],(ll)f[i-1][j][1]*(i-j-1)); Update(f[i][j][0],(ll)f[i-1][j][0]*(i-j-2)); } } printf("%lld\n",f[n][0][0]); return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/9432028.html

相关资源：JAVA上百实例源码以及开源项目