【BZOJ1925】【SDOI2010】地精部落

动态规划即可。

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

考虑第二个数:

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

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

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

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

用滚动数组实现,时间复杂度 O(n^2) ,空间复杂度 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://www.q234rty.top/2016/07/08/bzoj1925/

隐藏