SGU 222.Little Rooks

题意：

　　求在n*n（n<10）的棋盘上放k个车（水平竖直行走）的方案数。

Solution

　　SGU220的简化版。直接DP

　　显然当k>n时,ans=0;

　　f[i][j]代表在前n行放了j个棋子.

　　转移方程

　　f[i][j]=f[i-1][j]+f[i-1][j-1]*(n-j+1);

#include <iostream>

using namespace std;

int f[][], n, m, ans;

int main() {

    ios::sync_with_stdio ();

    cin >> n >> m;

    if (m <= n) {

        f[][]=;

        for (int j = ; j <= m; j++)

            for (int i = ; i <= n; i++) {

                if (j > ) f[i][j] = f[i - ][j - ] * (n - j + ) + f[i-][j];

                if (j == m) ans += f[i][j];

            }

        if (m == ) ans = ;

    }

    cout << ans << endl;

}

Code

巴特西

SGU 222.Little Rooks

最新文章

热门文章