HDU/HDOJ 2151 Worm(DP)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <string>
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;
    }
}
*/

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 2151 Worm(DP)》有917个想法

  1. 应该是DFS吧。感觉也不像是DFS。更像是不断递归的。博主写的BFS有问题,将BFS改为:
    void BFS(int vis, int time)
    {
    if(time==M && vis==T)
    {
    ++cnt;
    return ;
    }
    /*if(vis == T)
    return;*/

    if(visN)
    return;
    if(time>M)
    return;

    if(vis >= 2)
    BFS(vis-1, time+1);
    if(vis <= N-1)
    BFS(vis+1, time+1);
    }后可以运行例子中的测试用例,但是提交后超时了。怎么办呢?

    1. 博主,请问第二种BFS的方法看起来像是DFS呢。这个BFS怎么理解好一些?第一种DP方法中初始化dp[0][P] = 1;为什么不是0呢?谢谢了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注