首页 > 代码库 > HDU 4832 Chess

HDU 4832 Chess

2024-07-16 11:25:43   221人阅读

同样是百度之星的题目。
刚开始看题目，觉得这是一道搜索的题，于是就萌生了找题解的想法。一开始就没有斗志，当然不会做出这道题的啦。

可是看完题解恍然大悟，原来是DP，而且很简单的一道DP。
再一次失败，说明了看题解真的不是一个好习惯。我要改！ 我要改！！

其实基本的思想就是把这个二维移动分开，变成一维的移动，最后加上组合数就OK了。

下面的是代码，虽然是自己敲的，但是还是剽窃过来的。。。。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int mod = 9999991;const int maxn = 1010;#define LL long longLL 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));    }}
View Code

 


联系
我们