51nod 1327 棋盘游戏——延迟决策的dp

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1327

因为一列填1个或0个（或0个！！！），而一行不知填多少个，所以按列dp。

发现 l 和 r 的限制略有不同。大约是 l 如果先不填的话，在列向右移动的过程中可能就不能填了；而 r 一旦遇到，之后想什么时候填都可以。

所以可以记录空下了几列，遇到 l 的右边界时再处理该行，即从之前空下的列中选一个给该行；如果一下有多个 l 的右边界，乘上一个排列即可。

对于 r ，只要记录遇到过左边界的 r 里有多少个每填即可。

所以 dp[ i ][ j ][ k ] 表示第 i 列，空下 j 列，有 k 个遇到过的 r 没填的方案数。

注意一列可以不填！所以这一列不填或者填 l 这两种状态不要混起来，最好分开算。

注意不仅4个转移都要乘上选 l 的排列，它们自己都有自己的方案数！！！特别是这一列填 l 的时候，要乘 l [ i ] ！！！！！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,M=,mod=1e9+;

int n,m,l[M],r[M],dp[M][M][N],A[M][M],ans;

void Up(int &x,int y){x+=y;x>=mod?x-=mod:;}

void upd(int &x){x>=mod?x-=mod:;}

void init()

{

  for(int i=;i<=m;i++)A[i][]=;

  for(int i=;i<=m;i++)

    for(int j=;j<=m;j++)

      A[i][j]=A[i-][j-]+A[i-][j],upd(A[i][j]);

  for(int j=,ml=;j<=m;j++)

    {

      ml=(ll)ml*j%mod;

      for(int i=j;i<=m;i++)

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

    }

}

int main()

{

  scanf("%d%d",&n,&m);init();

  for(int i=,u,v;i<=n;i++)

    {

      scanf("%d%d",&u,&v);

      l[u]++;r[m-v+]++;

    }

  dp[][][]=;

  int yl=,rd=,yr=;

  for(int i=;i<=m;i++)

    {

      rd+=l[i-]-r[i];

      for(int j=max(,l[i]-);j<=i--yl;j++)

    for(int k=;k<=yr;k++)

      {

        if(!dp[i][j][k])continue;

        if(l[i])

        Up(dp[i+][j-(l[i]-)][k+r[i]],(ll)dp[i][j][k]*A[j][l[i]-]%mod*l[i]%mod);

        if(j>=l[i])

        Up(dp[i+][j+-l[i]][k+r[i]],(ll)dp[i][j][k]*A[j][l[i]]%mod);

        if(k+r[i]&&j>=l[i])

        Up(dp[i+][j-l[i]][k+r[i]-],(ll)dp[i][j][k]*A[j][l[i]]%mod*(k+r[i])%mod);

        if(rd&&j>=l[i])

        Up(dp[i+][j-l[i]][k+r[i]],(ll)dp[i][j][k]*A[j][l[i]]%mod*rd%mod);

      }

      yl+=l[i];yr+=r[i];

    }

  for(int i=;i<=m;i++)ans+=dp[m+][i][],upd(ans);

  printf("%d\n",ans);

  return ;

}

巴特西

51nod 1327 棋盘游戏——延迟决策的dp

最新文章

热门文章