【BZOJ1925】【SDOI2010】地精部落

动态规划即可。

定义f(i,j)f(i,j)[1,i][1,i]的排列, 第一个数为jj第二个数比第一个数小,且满足题目要求的方案数。

考虑第二个数:

当第二个数不是j1j-1时,交换jjj1j-1,注意到这两个数不相邻(因此互不影响)并且与其它数的大小关系相同,所以交换后得到的仍是合法的方案。所以此时的方案数为f(i,j1)f(i,j-1)

当第二个数是j1j-1时,去掉第一个数,并将所有x>j1x>j-1变成x1x-1,此时原排列变成[1,i1][1,i-1]的排列,且第二个数比第一个数大,并满足题目要求。将每个数xx变成ixi-x,此时仍为[1,i1][1,i-1]的排列,且第二个数比第一个数小,第一个数为ij+1i-j+1仍满足题目要求。于是方案数为f(i1,ij+1)f(i-1,i-j+1)

于是f(i,j)=f(i,j1)+f(i1,ij+1)f(i,j)=f(i,j-1)+f(i-1,i-j+1),初值为f(1,1)=1f(1,1)=1

最后ans=i=1nf(n,i)ans=\sum_{i=1}^{n}f(n,i)

用滚动数组实现,时间复杂度O(n2)O(n^2),空间复杂度O(n)O(n)

Code

#include <cstdio>
#include <cstring>
using namespace std;
int dp[2][4201];
int main(){
    int n,p;
    scanf("%d%d",&n,&p);
    int cur=1;
    memset(dp[0],0,sizeof(dp[0]));
    dp[0][1]=1;
    for(int i=2;i<=n;i++){
        memset(dp[cur],0,sizeof(dp[cur]));
        for(int j=1;j<=i;j++)
            dp[cur][j]=(dp[cur][j-1]+dp[cur^1][i-j+1])%p;
        cur^=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        (ans+=dp[cur^1][i])%=p;
    printf("%d",ans*2%p);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2016/07/08/bzoj1925/

隐藏