【DP】中国象棋 |
您所在的位置：网站首页 › 中国象棋大家 › 【DP】中国象棋 |
|
题目描述
这次小可可想解决的难题和中国象棋有关。在一个 N 行 M 列的棋盘上，让你放若干个炮（可以是 0 个），使得没有任何一个炮可以攻击另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮能攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋中。你也来和小可可一起锻炼一下思维吧！ 输入一行包含两个整数 N, M，之间由一个空格隔开。 输出总共的方案数。由于该值可能很大，只需给出方案数模 9999973 的结果。 样例输入 1 3 样例输出 7 数据范围限制30% 的数据中 N 和 M 均不超过 6 50% 的数据中 N 和 M 至少有一个数不超过 8 100% 的数据中 N 和 M 不超过 100 解只要每行每列摆的数量不超过2。 设f[i][l1][l2]为截止i行，有l1列摆了1个炮，有l2列摆了2个炮。 然后分6种情况讨论… …（头裂 Code #include int n,m; long long ans; long long f[101][101][101],C[1001],mod = 9999973; int main(){ scanf("%d%d",&n,&m); for(int i = 1; i >1)%mod; f[0][0][0] = 1; for(int i = 1; i 1) f[i][l1][l2] = (f[i][l1][l2] + f[i-1][l1-2][l2] * C[(m-(l1-2+l2))] % mod) %mod; //0放2 if(l2>0&&l1>0) f[i][l1][l2] = (f[i][l1][l2] + f[i-1][l1][l2-1] * (m-(l1+l2-1))*(l1) % mod) %mod; //0放1,1放1 if(l2>1) f[i][l1][l2] = (f[i][l1][l2] + f[i-1][l1+2][l2-2]*C[l1+2] % mod) %mod; //1放2 } for(int l1 = 0; l1 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |