本文主要是介绍矩阵中的DP题 放象棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目的意思很简单：在n * m的矩阵中放置若干个炮（可以不放），使得没有一个炮可以攻击另外一个炮。炮的攻击方式就不用多说了。答案mod 9999973。
这个题目一开始我想得很接近了，但没想到用DP，觉得是组合数学。首先可以把问题转化一下：没有一列或一行有两个以上的炮，这样炮于炮之间就不能攻击了。也就是说，每行或每列，要么不放炮，要么放一个或两个，有三种可能。又因为行列是交错的，每放一个炮，对行列都有影响。以前做过一道类似的题，好像叫“一笔画”，是对每一行进行处理，然后把列的信息保存下来。这题也是这样。
记f（i，j，k）为当前对第i行决策，已经有j列有一个炮，k列有两个炮，至于没有炮的有多少列，这个只需要用总列数m - j - k，把m - j - k记为p。那么，对于这一行，我们最多只能放两个棋， 有种方案：
1.放一个在没有炮的列，那么前一个状态是f（i - 1，j - 1，k），那么有p + 1列是没有炮的，放的棋子就有p + 1种选择。
2.放两个在没有炮的列，那么前一个状态是f（i - 1，j - 2，k），那么有p + 2列是没有炮的，放的棋子就有C（p + 2， 2）种选择。
3.放一个在有一个炮的列，那么前一个状态是f（i - 1，j + 1，k - 1），有j + 1列是有一个炮的，放的棋子就有j + 1种选择。
4.放两个在有一个炮的列，那么前一个状态是f（i - 1，j + 2，k - 2），有j + 1列是有一个炮的，放的棋子就有C（j + 2，2）种选择。
5.放一个在没有炮的列，再放一个在有一个炮的列，那么前一个状态是f（i - 1，j，k - 1），选择有（p + 1） * （j + 1）。
6.不放，前一个状态是f（i - 1，j，k）。
最后输出f（n）的和就可以了。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;const LL mod = 9999973;
const int N = 107;int n, m;
LL f[N][N], g[N][N];
// flag为false,C(a, 1)，为true,C(a, 2)
LL C(int a, bool flag)
{if (flag) return (LL) a * (a - 1) / 2;return (LL) a;
}void plus(LL &s, LL t)
{s = (s + t) % mod;
}int main()
{freopen("cchess.in", "r", stdin);freopen("cchess.out", "w", stdout);scanf("%d%d\n", &n, &m);g[0][0] = 1LL;for (int i = 0; i < n; i ++){memset(f, 0, sizeof(f));for (int a = 0; a <= m; a ++)for (int b = 0; a + b <= m; b ++){plus(f[a][b], g[a][b]);if (a > 0) plus(f[a][b], g[a - 1][b] * C(m - a - b + 1, 0));if (a > 1) plus(f[a][b], g[a - 2][b] * C(m - a - b + 2, 1));if (b > 0) plus(f[a][b], g[a + 1][b - 1] * C(a + 1, 0));if (b > 1) plus(f[a][b], g[a + 2][b - 2] * C(a + 2, 1));if (b > 0) plus(f[a][b], g[a][b - 1] * C(m - a - b + 1, 0) * C(a, 0));}for (int a = 0; a <= m; a ++)for (int b = 0; b <= m; b ++) g[a][b] = f[a][b];}LL ans = 0;for (int a = 0; a <= m; a ++)for (int b = 0; b <= m; b ++)plus(ans, f[a][b]);printf("%I64d\n", ans);return 0;
}
这篇关于矩阵中的DP题 放象棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
