打表过……
又是一道5EMB+的dp基础题，开心。只需检测对应当前坐标（设为(a,b)）的(a-1,b-2)位置和(a-2,b-1)位置即可。 附C++代码：
#include <bits/stdc++.h> using namespace std; int main() { int T, dp[31][31]={{0}}; dp[2][3]=dp[3][2]=1; for(int i=3; i<31; i++) for(int j=3; j<31; j++) { dp[i][j]+=dp[i-1][j-2]; dp[i][j]+=dp[i-2][j-1]; } cin>>T; for(int I=0; I<T; I++) { int a, b; cin>>a>>b; cout<<"Chessboard #"<<I+1<<':'<<dp[a][b]<<endl; } return 0; }
一道简单的dp，可能因为是冷门所以分高一些？可以打表但是比较麻烦。我不太会元编程一类的黑魔法，所以没法编译期打表了。
下面是程序，把棋盘扩大一圈用作哨兵，可以减少判断的开销。
#include <iostream> using namespace std; int t, h, w, board[32][32]; void process() { board[2][2] = 1; for (int i = 2; i < 32; ++i) for (int j = 2; j < 32; ++j) board[i][j] += board[i - 1][j - 2] + board[i - 2][j - 1]; board[2][2] = 0; } int main() { process(); cin >> t; for (int i = 1; i <= t; ++i) { cin >> h >> w; printf("Chessboard #%d:%d\n", i, board[h + 1][w + 1]); } }
打表过……
又是一道5EMB+的dp基础题，开心。只需检测对应当前坐标（设为(a,b)）的(a-1,b-2)位置和(a-2,b-1)位置即可。
附C++代码：
一道简单的dp，可能因为是冷门所以分高一些？可以打表但是比较麻烦。我不太会元编程一类的黑魔法，所以没法编译期打表了。
下面是程序，把棋盘扩大一圈用作哨兵，可以减少判断的开销。