同样是百度之星的题目。
刚开始看题目，觉得这是一道搜索的题，于是就萌生了找题解的想法。一开始就没有斗志，当然不会做出这道题的啦。
可是看完题解恍然大悟，原来是DP，而且很简单的一道DP。
再一次失败，说明了看题解真的不是一个好习惯。我要改！ 我要改！！
其实基本的思想就是把这个二维移动分开，变成一维的移动，最后加上组合数就OK了。
下面的是代码，虽然是自己敲的，但是还是剽窃过来的。。。。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int mod = 9999991; const int maxn = 1010; #define LL long long LL sum[2][maxn], dp[2][maxn][maxn]; LL C[1010][1010]; void init() { memset(sum, 0, sizeof(sum)); memset(dp, 0, sizeof(dp)); for(int i = 0; i < maxn; i++) C[i][i] = 1, C[i][0] = 1; for(int i = 2; i < maxn; i++) for(int j = 1; j < i; j++) C[i][j] =(C[i-1][j] + C[i-1][j-1]) % mod; } void solve(int n, int k, int t, int p) { dp[p][0][t] = 1; sum[p][0] = 1; for(int i = 1; i <= k; i++) { for(int j = 1; j <= n; j++) { if(j - 1 > 0) dp[p][i][j] += dp[p][i-1][j-1]; if(j - 2 > 0) dp[p][i][j] += dp[p][i-1][j-2]; if(j + 1 <= n) dp[p][i][j] += dp[p][i-1][j+1]; if(j + 2 <= n) dp[p][i][j] += dp[p][i-1][j+2]; dp[p][i][j] %= mod; sum[p][i] = (sum[p][i] + dp[p][i][j]) % mod; } } return ; } LL getans(int k) { LL ans = 0; for(int i = 0; i <= k; i++) ans = ans + (((C[k][i] * sum[1][i]) % mod) * sum[0][k - i]) % mod; return ans % mod; } int main() { int t, n, m, k, x, y; cin >> t; for(int Case = 1; Case <= t; Case++) { scanf("%d%d%d%d%d", &n, &m, &k, &x, &y); init(); solve(n,k,x,0); solve(m,k,y,1); printf("Case #%d:\n%I64d\n", Case, getans(k)); } }
原文：http://www.cnblogs.com/ye8370/p/3899387.html
