题目链接：hdu 4832 Chess

题目大意：略。（注意King只能走周围8格）

解题思路：将水平和竖直分开考虑，l[i]表示竖直上走i步不出界的种数，r[i]表示水平上走i步不出界的种数，然后枚举水平竖直走的步数（相加为k），并且要乘以组合数。因为确定步数了但是还要考虑先后的关系。
处理步数的时候，开一个二维数组dp[i][j],表示i步，位置在j的种数，j为偏移，j-k为负数表示在起始点左/上的|j k|位置，j-k为正数表示在起点右/下的|j k|的位置上。

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; const int N = 1010; const ll MOD = 9999991; int n, m, k, x, y; ll l[N], r[N], g[N][N*2], c[N][N]; void cat (ll* a, int x, int t) { memset(g, 0, sizeof(g)); g[0][k] = 1; int up = k-(x-1); int down = k+(t-x); for (int i = 1; i <= k; i++) { for (int j = up; j <= down; j++) { if (g[i-1][j]) { if (j != up) { g[i][j-1] = (g[i][j-1] + g[i-1][j]) % MOD; if (j != up+1) g[i][j-2] = (g[i][j-2] + g[i-1][j]) % MOD; } if (j != down) { g[i][j+1] = (g[i][j+1] + g[i-1][j]) % MOD; if (j != down-1) g[i][j+2] = (g[i][j+2] + g[i-1][j]) % MOD; } } a[i-1] = (a[i-1] + g[i-1][j]) % MOD; } } for (int i = up; i <= down; i++) a[k] = (a[k] + g[k][i]) % MOD; } void input () { for (int i = 0; i < N; i++) { c[i][0] = c[i][i] = 1; for (int j = 0; j < i; j++) c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD; } } void init () { //scanf("%d%d%d%d%d", &n, &m, &k, &x, &y); cin >




> n >> m >> k >> x >> y; memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r)); cat(l, x, n); cat(r, y, m); } ll solve () { ll ans = 0; for (int i = 0; i <= k; i++) ans = (ans + (l[i] * r[k-i]) % MOD * c[k][i])%MOD; return ans; } int main () { input(); int cas; cin >> cas; for (int i = 1; i <= cas; i++) { init(); //printf("Case #%d:\n%lld\n", i, solve()); cout << "Case #" << i << ":" << endl; cout << solve() << endl; } return 0; }

hdu 4832 Chess(计数+dp)

题目链接：hdu 4832 Chess