51nod1327 棋盘游戏

远古大坑

神仙DP状态设计题

https://blog.csdn.net/white_elephant/article/details/83592103

从行的角度入手，无论如何都要状压

每列最多放一个，所以从列的角度入手

每列会左端点结束，右端点出现，以及空位

个数设为：l[i],r[i],md[i]

直接决定当前列填在哪一行很困难，若直接记录还有多少行左半边没有填，那么并不知道哪些行的左半边之后会消失，无法转移

所以在这个左半边消失的时刻进行安排位置！

只要考虑之前预留了多少列即可，这些列都是可以用的

右半边？

预留就不行了，因为“起点”不一样，不一定都能用

但是终点一样，这次没有填的右部分，下一列还是可以填，所以直接转移

状态：f[i][j][k]“填完前i列，还有j列是空的，右半部分还有k行左端点出现在i及之前，且没有放置”的方案数

转移枚举填什么即可

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

#define pb push_back

#define solid const auto &

#define enter cout<<endl

#define pii pair<int,int>

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{

const int N=;

const int M=;

const int mod=1e9+;

int A[M][M];

int jie[M];

int n,m,f[M][M][N];

int l[M],r[M],md[M];

int ad(int x,int y){

    return (x+y)>=mod?x+y-mod:x+y;

}

void inc(int &x,int y){

    x=ad(x,y);

}

int mul(int x,int y){

    return (ll)x*y%mod;

}

int main(){

    rd(n);rd(m);

    if(*n>m){

        puts("");return ;

    }

    jie[]=;

    for(reg i=;i<=m;++i) jie[i]=(ll)jie[i-]*i%mod;

    A[][]=;

    for(reg i=;i<=m;++i){

        A[i][]=;

        for(reg j=;j<=i;++j){

            A[i][j]=ad(A[i-][j],A[i-][j-]);

        }

    }

    for(reg i=;i<=m;++i){

        for(reg j=;j<=i;++j){

            A[i][j]=(ll)A[i][j]*jie[j]%mod;

        }

    }

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

        int L,R;rd(L);rd(R);

        R=m-R+;

        ++l[L];++r[R];

        for(reg j=L+;j<R;++j){

            ++md[j];

        }

    }

    f[][][]=;

    for(reg i=;i<m;++i){

        for(reg j=;j<=i;++j){

            for(reg k=;k<=n;++k){

                int lp=f[i][j][k];

                if(lp){

                    if(j+-l[i+]>=) inc(f[i+][j+-l[i+]][k+r[i+]],mul(lp,A[j+][l[i+]]));

                    if(j-l[i+]>=&&k+r[i+]>) inc(f[i+][j-l[i+]][k+r[i+]-],mul(lp,mul(A[j][l[i+]],k+r[i+])));

                    if(j-l[i+]>=) inc(f[i+][j-l[i+]][k+r[i+]],mul(lp,mul(A[j][l[i+]],md[i+])));

                }

            }

        }

    }

    ll ans=;

    for(reg j=;j<=m;++j) ans=ad(ans,f[m][j][]);

    ot(ans);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/

考虑从列入手简单

但是直接记录剩下多少个没填很难，因为结束位置不同

所以考虑在最后结束位置进行分配，只要记录之前剩下多少

一种变相的对未来承诺，或者说是预留

巴特西

51nod1327 棋盘游戏

最新文章

热门文章