内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个 n×m 的棋盘，在上面放置若干个棋子，要求任一行任一列至多只能有两颗棋子，求一共有多少种放置方案。
由于方案数可能会很大，对方案数模 10^9+7。一只棋子都不放也算一种方案。
输入格式
两个整数表示 n 与 m
输出格式
单个整数：表示方案数模 10^9+7
数据范围
对于 20% 的数据，1≤n,m≤10
对于 100% 的数据，1≤n,m≤100
样例数据
输入:
2 3
输出:
49
输入:
1 3
输出:
7
题目解析：状态DP 分类讨论
1. #include <bits/stdc++.h> 2. using namespace std; 3. const int P=1e9+7; 4. long long dp[2][101][101][101];//滚动数组 做空间优化 5. int main() 6. { 7. int n,m; 8. cin>>n>>m; 9. //初始化dp[0] 10. for(int x=0;x<=m;x++){ 11. for(int y=0;y<=m;y++){ 12. if(x+y>m) break; 13. int z=m-x-y; 14. dp[0][x][y][z]=1; 15. } 16. } 17. //从dp[1]到dp[n] 18. for(int i=1;i<=n;i++){ 19. for(int x=0;x<=m;x++){ 20. for(int y=0;y<=m;y++){ 21. if(x+y>m) break; 22. int z=m-x-y; 23. if(y+2*z>2*(n-i)) continue; 24. int _i=i&1; 25. int _isub1=(i-1)&1; 26. //分类讨论： 27. //1)第i行用了0个1 dp[i-1][x][y][z] 28. dp[_i][x][y][z]=dp[_isub1][x][y][z]; 29. //2)第i行用了1个1 dp[i-1][x-1][y+1][z],dp[i-1][x][y-1][z+1] 30. if(x) dp[_i][x][y][z]+=x*dp[_isub1][x-1][y+1][z]; 31. if(y) dp[_i][x][y][z]+=y*dp[_isub1][x][y-1][z+1]; 32. //3)第i行用了2个1 33. if(x>1) dp[_i][x][y][z]+=x*(x-1)/2*dp[_isub1][x-2][y+2][z]; 34. if(y>1) dp[_i][x][y][z]+=y*(y-1)/2*dp[_isub1][x][y-2][z+2]; 35. if(x&&y) dp[_i][x][y][z]+=y*x*dp[_isub1][x-1][y][z+1]; 36. dp[_i][x][y][z]%=P; 37. 38. } 39. } 40. } 41. //输出dp[n][m][0][0] 42. cout<<dp[n&1][m][0][0]; 43. return 0; 44. }
