Blog·Tanky WooABOUTRSS

HDU/HDOJ 2151 Worm(DP)

23 Nov 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2151

先开始用的BFS,结果爆栈了,然后换成DP~~~

#include 
#include 
using namespace std;

int N, P, M, T;

// dp[M][T];
// 表示在M时间上,走到T的方案数
// dp[M][T] = dp[M-1][T-1] + dp[M-1][T+1]
// 初始化dp[0][P] = 1;
int dp[105][105];

int main()
{
    while(cin >> N >> P >> M >> T)
    {
        memset(dp, 0, sizeof(dp));
        dp[0][P] = 1;
        for(int i=1; i<=M; ++i)
            for(int j=1; j<=N; ++j)
            {
                if(j-1 >= 1)
                    dp[i][j] += dp[i-1][j-1];
                if(j+1 <= N)
                    dp[i][j] += dp[i-1][j+1];
            }

        cout << dp[M][T] << endl;
    }
}

/*
int cnt;

void BFS(int vis, int time)
{
    if(time==M && vis==T)
    {
        ++cnt;
        return ;
    }
    if(vis == T)
        return;

    if(vis<1 || vis>N)
        return;

    if(vis >= 2)
        BFS(vis-1, time+1);
    if(vis <= N-1)
        BFS(vis+1, time+1);
}

int main()
{
    while(cin >> N >> P >> M >> T)
    {
        cnt = 0;
        BFS(P, 0);
        cout << cnt << endl;
    }
}
*/