棋盘游戏 51Nod - 1327

题解：在放置棋子时仅仅要求左右满足条件与n的顺序无关，考虑一个二维dp数组,dp[i][j]代表放到了第i列还有j列没有放棋子，但是这个二维dp没有维护右限的信息，所以考虑增加一维代表有多少行到达了右限但没有棋子，将l和r区间的限制统计，可以得到dp转移方程：

 

 

dp[a+1][b+1-l[a+1]][c+r[a+1]]+=dp[a][b][c]*sum[b+1][l[a+1]]%mod；

枚举到当第i列，有l[i]行必须要放左区间了，从空的列中选择放入当前列不放入，同时加上到达右限的区间

dp[a+1][b-l[a+1]][c+r[a+1]]+=dp[a][b][c]*sum[b][l[a+1]]%mod*num[a+1]%mod; 

枚举到当第i列，有l[i]行必须要放左区间了，从空的列中选择放入当前列放作用于不在左右限制的行，同时加上到达右限的区间

dp[a+1][b-l[a+1]][c+r[a+1]-1]+=dp[a][b][c]*sum[b][l[a+1]]%mod*(c+r[a+1])%mod;

枚举到当第i列，有l[i]行必须要放左区间了，从空的列中选择放入但是当前列放入右限区间，同时加上到达右限的区间

比较难！！！！！

ac代码：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define ll long long
using namespace std;
int read(){
    char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');
    if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')
        x=x*10+c-'0';return x*y;
}
const int maxn=2e2+10;
const ll mod=1e9+7;
ll dp[maxn][maxn][55];
ll sum[maxn][maxn];
int l[maxn],r[maxn],num[maxn];
int main( ){
    int n=read(),m=read();
    memset(dp,0,sizeof(dp));
    for(int a=0;a<=m;a++){
        sum[a][0]=1;
        for(int b=1;b<=a;b++) sum[a][b]=sum[a][b-1]*(a-b+1)%mod;
    }
    for(int a=1;a<=n;a++){
        int u=read(),v=read();
        l[u]++,r[m-v+1]++;
        num[u+1]++;
        num[m-v+1]--;
    }
    for(int a=2;a<=m;a++) num[a]+=num[a-1];
    dp[0][0][0]=1;
    for(int a=0;a<m;a++){
        for(int b=0;b<=a;b++){
            for(int c=0;c<=n;c++){
                if(!dp[a][b][c]) continue;
                if(b+1>=l[a+1])
                    dp[a+1][b+1-l[a+1]][c+r[a+1]]+=dp[a][b][c]*sum[b+1][l[a+1]]%mod,dp[a+1][b+1-l[a+1]][c+r[a+1]]%=mod;
                if(b>=l[a+1])
                    dp[a+1][b-l[a+1]][c+r[a+1]]+=dp[a][b][c]*sum[b][l[a+1]]%mod*num[a+1]%mod,dp[a+1][b-l[a+1]][c+r[a+1]]%=mod;
                if(b>=l[a+1]&&c+r[a+1]>=1)
                    dp[a+1][b-l[a+1]][c+r[a+1]-1]+=dp[a][b][c]*sum[b][l[a+1]]%mod*(c+r[a+1])%mod,dp[a+1][b-l[a+1]][c+r[a+1]-1]%=mod;
            }
        }
    }
    ll ans=0;
    for(int a=0;a<=m;a++) ans=(ans+dp[m][a][0])%mod;
    printf("%lld\n",ans);
}

 

本文地址：https://blog.csdn.net/qq_40584551/article/details/107321297