欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

棋盘游戏 51Nod - 1327

程序员文章站 2022-03-20 12:56:15
题解:在放置棋子时仅仅要求左右满足条件与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]行必须要放左区间了,从空的列中选择放入当前列不放入,同时加上到达右限的区间d....

题解:在放置棋子时仅仅要求左右满足条件与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