【BZOJ】1925: [Sdoi2010]地精部落 DP+滚动数组

时间：2021-08-01 00:05:11

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1925

题意:输入一个数N(1 <= N <= 4200),问将这些数排列成折线型有多少中合法的排列；折线形即一个数比相邻的数都大或者都小;

如:1 3 2 4就是一个折线型；

思路:f[i,j]表示排列的前i个数是以1...j为开头的第一位下降的合法个数；

转移公式为:f[i][j] = f[i][j-1] + f[i-1][i-j]; f[i][j-1]就不把第j个数添加到首位的原来的个数值；f[i-1][i-j]是当j为第一位时，由于第一位要是下降的，所以第二位要小于j,同时第二位还要是递增的；由于递增和递减的对称性，我们可以转而求第二位大于j，并且第二位是递减的。这样大于j的个数就是i-j,从第二位开始的递减就是 i-1个数；即f[i-1][i-j];

实现细节:至于滚动数组就是节约内存，之和前一个[i-1]这一维有关，即只用第一维开成2即可；最后还要*2，由于是对称的；但是需特判n = 1；

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define inf 0x7fffffff

#define pow(a) (a)*(a)

typedef long long ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

#define N 4204

int dp[][N];

int main()

{

    int n,mod;

    read2(n,mod);

    if(n == ) return puts(""),;

    int pre = ,cur = ;

    dp[pre][] = ;

    for(int i = ;i <= n;i++){

        pre ^= ,cur ^= ;

        for(int j = ;j <= n;j++){

            dp[pre][j] = dp[pre][j-];

            if(i >= j) dp[pre][j] += dp[cur][i-j];

            if(dp[pre][j] > mod) dp[pre][j] -= mod;

        }

    }

    printf("%d\n",(dp[pre][n]*)%mod);

    return ;

}

相关文章