【BZOJ1925】【SDOI2010】地精部落

Author Avatar
q234rty 7月 08, 2016

动态规划即可。

定义 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/

隐藏