CF1081C Colorful Bricks

思路：

dp[i][j]表示到第i个砖块为止共计有j个砖块和它左边的砖块颜色不同。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4  const int MOD = 998244353;
 5  ll dp[2005][2005];
 6  int main()
 7 {
 8     int n, m, k;
 9     while (cin >> n >> m >> k)
10     {
11         memset(dp, 0, sizeof dp);
12         dp[1][0] = m;
13         for (int i = 2; i <= n; i++)
14         {
15             for (int j = 0; j < i; j++)
16             {
17                 dp[i][j] = dp[i - 1][j];
18                 if (j > 0)
19                 {
20                     dp[i][j] += dp[i - 1][j - 1] * (m - 1);
21                     dp[i][j] %= MOD;
22                 }
23             }
24         }
25         cout << dp[n][k] << endl;
26     }
27     return 0;
28 }