题目来源： TopCoder
基准时间限制：1 秒 空间限制：131072 KB 分值: 640 难度：8级算法题
收藏
关注
有一个N行M列的棋盘，即该棋盘被分为N*M格。现在向棋盘中放棋子，每个格子中最多放一个棋子，也可以一个不放。放完棋子后需要满足如下要求：
1）对于第i行来说，其从左往右的前left[i] 个格子（即最左侧的left[i] 个连续的格子）中恰好一共有1个棋子；
2）对于第i行来说，其从右往左的前right[i]个格子（即最右侧的right[i]个连续的格子）中恰好一共有1个棋子；
3）对于每一列来说，这一列上的所有格子内含有的棋子数不得超过1个。
其中，1）与2）条件中，对所有 i 满足 left[i]+right[i] <= M，即两个区间不会相交。
问，符合上述条件情况下棋子的不同放法一共有多少种？输出放法的个数 mod 1,000,000,007后的结果。
例如样例中，只有如下图一种方法。
Input
第一行包含两个整数，N，M，其中1<=N<=50,2<=M<=200.之后有N行，每行两个数left[i],right[i],其中，1<=left[i],right[i]<=M,且 left[i]+right[i] <= M。
Output
一个整数，即符合条件的方案数mod 1,000,000,007后的结果。
Input示例
2 41 22 1
Output示例
1
【分析】
奇葩dp
去看别的宝宝的讲解吧...
【代码】
//51nod 1327 棋盘游戏
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int mxn=205;
const int mod=1e9+7;
int n,m,T,lef,rig,ans;
int L[mxn],R[mxn],p[mxn];
ll fac[mxn],C[mxn][mxn],dp[mxn][mxn][mxn];
inline void init()
{
fac[0]=1;fo(i,0,200) C[i][0]=1;
fo(i,1,200) fac[i]=fac[i-1]*i%mod;
fo(i,1,200) fo(j,1,200) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int main()
{
init();
scanf("%d%d",&n,&m);
fo(i,1,n)
{
scanf("%d%d",&lef,&rig);
L[lef]++,R[m-rig+1]++;
fo(j,lef+1,m-rig) p[j]++;
}
dp[0][0][0]=1;
fo(i,0,m)
fo(j,0,m)
fo(k,0,n) if(dp[i][j][k] && k+R[i+1]<=n)
{
if(j-L[i+1]+1>=0)
(dp[i+1][j-L[i+1]+1][k+R[i+1]]+=dp[i][j][k]*C[j+1][L[i+1]]%mod*fac[L[i+1]]%mod)%=mod;
if(j-L[i+1]>=0)
(dp[i+1][j-L[i+1]][k+R[i+1]]+=dp[i][j][k]*p[i+1]%mod*C[j][L[i+1]]%mod*fac[L[i+1]]%mod)%=mod;
if(j-L[i+1]>=0 && k+R[i+1]>0)
(dp[i+1][j-L[i+1]][k+R[i+1]-1]+=dp[i][j][k]*(k+R[i+1])%mod*C[j][L[i+1]]%mod*fac[L[i+1]]%mod)%=mod;
}
fo(i,0,m) ans=(ans+dp[m][i][0])%mod;
printf("%d\n",ans);
return 0;
}