704
動態規劃-hdoj-4832-百度之星2014初賽第二場
Chess
Problem Description
小度和小良最近又迷上了下棋。棋盤一共有N行M列，我們可以把左上角的格子定為(1,1)，右下角的格子定為(N,M)。在他們的規則中，“王”在棋盤上的走法遵循十字路線。也就是說，如果“王”當前在(x,y)點，小度在下一步可以移動到(x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+2, y), (x-2, y), (x, y+2), (x, y-2) 這八個點中的任意一個。
小度覺得每次都是小良贏，沒意思。為了難倒小良，他想出了這樣一個問題：如果一開始“王”在(x0,y0)點，小良對“王”連續移動恰好K步，一共可以有多少種不同的移動方案？兩種方案相同，當且僅當它們的K次移動全部都是一樣的。也就是說，先向左再向右移動，和先向右再向左移動被認為是不同的方案。
小良被難倒了。你能寫程序解決這個問題嗎？
Input
輸入包括多組數據。輸入數據的第一行是一個整數T(T≤10)，表示測試數據的組數。
每組測試數據隻包括一行，為五個整數N,M,K,x0,y0。(1≤N,M,K≤1000,1≤x0≤N,1≤y0≤M)
Output
對於第k組數據，第一行輸出Case #k:，第二行輸出所求的方案數。由於答案可能非常大，你隻需要輸出結果對9999991取模之後的值即可。
Sample Input
2
2 2 1 1 1
2 2 2 1 1
Sample Output
Case #1:
2
Case #2:
4
Source
2014年百度之星程序設計大賽 - 初賽（第二輪）
分析：原始的dp[i][j][k],在（i，j）位置上走k步的方案數，效率低下。注意到行與列相對獨立。所以dpx[ ] dpy[] c[][]都用上。
最後更新：2017-04-03 08:26:19