HDOJ 1085 Holding Bin-Laden Captive!

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1085

HOHO, [s:19] 终于碰到一个不是简单套模板的了,这里要理解了模板才能做的轻松。
万变不离其中。

题目给出了3种类型,每种既不是1个,又不是无限个。怎么办?
思路:
首先初始化,其次一个个来,每次记的把能取到值的范围扩大。
不好表达,我先把代码贴出来,然后再结合代码解答:

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
 #include <iostream>
using namespace std;
 
int c1[10000], c2[10000];
int num[4];
int main()
{
    int nNum;
    while(scanf("%d %d %d", &num[1], &num[2], &num[3]) && (num[1]||num[2]||num[3]))
    {
        int _max = num[1]*1+num[2]*2+num[3]*5;
        // 初始化
        for(int i=0; i<=_max; ++i)
        {
            c1[i] = 0;
            c2[i] = 0;
        }
        for(int i=0; i<=num[1]; ++i)
            c1[i] = 1;
        for(int i=0; i<=num[1]; ++i)
            for(int j=0; j<=num[2]*2; j+=2) 
                c2[j+i] += c1[i];
        for(int i=0; i<=num[2]*2+num[1]*1; ++i)       // 看到范围的变化了吗?
        {
            c1[i] = c2[i];
            c2[i] = 0;
        }
 
        for(int i=0; i<=num[1]*1+num[2]*2; ++i)
            for(int j=0; j<=num[3]*5; j+=5)
                c2[j+i] += c1[i];
        for(int i=0; i<=num[2]*2+num[1]*1+num[3]*5; ++i)
        {
            c1[i] = c2[i];
            c2[i] = 0;
        }
        int i;
 
        for(i=0; i<=_max; ++i)
            if(c1[i] == 0)
            {
                printf("%d\n", i);
                break;
            }
        if(i == _max+1)
            printf("%d\n", i);
    }
    return 0;
}

我在代码旁边写了一句话:”看到范围的变化了吗?“,大家好好理解下,范围是怎么变化的。

发布者

Tanky Woo

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

《HDOJ 1085 Holding Bin-Laden Captive!》有452个想法

  1. 楼主,你好。不开第二个数组,代码也能AC。我想问一下加上这个数组会带来哪些好处呢?会不会在某些数据下,出现WA?

  2. for(int i=0; i<=_max; ++i)
    {
    c1[i] = 0;
    c2[i] = 0;//在本题中,不需要对c2[i]赋值,可以删掉此行代码,这样的话可以提高减少一倍的时间
    }

    1. 1.不论你在后面是否把c2都赋为0了,在开头初始化为0是一个良好的习惯。
      2.这里占用的时间微乎其微,更不可能影响到时间复杂度,所以这里就算你在OJ上测试可以减少一倍,是没有意义的。
      就比如我以前遇到朝四个方向DFS,就算四个方向顺序不一样,都会造成有的甚至TLE,评价一个时间还是要看时间复杂度。

  3. 原型就是前面所说的
    for(i=2; i<=nNum; ++i) // —– ②
    {

    for(j=0; j<=nNum; ++j) // —– ③
    for(k=0; k+j<=nNum; k+=i) // —- ④
    {
    c2[j+k] += c1[j];
    }
    for(j=0; j<=nNum; ++j) // —- ⑤
    {
    c1[j] = c2[j];
    c2[j] = 0;
    }
    }
    只不过因为每个数的增加规律不一样而将三个表达式进行拆分,其实你的这种方法换句话说就是枚举。呵呵

  4. 最近看了你的母函数写的文章,又看到了这个题目
    根据你前面那篇关于母函数的最后一个例程写出下面的代码
    for (i=1;i<=num[1];i++)
    c1[i]+=c1[i-1];
    for (i=2;i<=num[1]+num[2]*2;i++)
    c1[i]+=c1[i-2];
    for (i=5;i<=maxnum;i++)
    c1[i]+=c1[i-5];

    谢谢你的文章 ,对我帮助非常大

发表评论

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