HDOJ 1171 Big Event in HDU

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

这题和HDOJ 1085类似,范围也是动态变化的。
这题很好,看到初始化了吗?并不是++i,而是 i+=value[1]
理解透彻了就知道为何。
其余的和HDOJ 1085差不多。

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
 // Author: Tanky Woo
// HDOJ 1171
 
 
#include <iostream>
using namespace std;
 
int c1[250010], c2[250010];
int value[55];
int amount[55];
int main()
{
    int nNum;
    while(scanf("%d", &nNum) && nNum>0)
    {
        memset(value, 0, sizeof(value));
        memset(amount, 0, sizeof(amount));
 
        int sum = 0;
        for(int i=1; i<=nNum; ++i)
        {
            scanf("%d %d", &value[i], &amount[i]);
            sum += value[i]*amount[i];
        }
        memset(c1, 0, sum*sizeof(c1[0]));
        memset(c2, 0, sum*sizeof(c2[0]));
        for(int i=0; i<=value[1]*amount[1]; i+=value[1])
            c1[i] = 1;
        int len = value[1]*amount[1];
        for(int i=2; i<=nNum; ++i)
        {
            for(int j=0; j<=len; ++j)
                for(int k=0; k<=value[i]*amount[i]; k+=value[i])
                {
                    c2[k+j] += c1[j];
                }
            len += value[i]*amount[i];
            for(int j=0; j<=len; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        for(int i= sum/2; i>=0; --i)
            if(c1[i] != 0)
            {
                printf("%d %d\n", sum-i, i);
                break;
            }
    }
    return 0;
}

发布者

Tanky Woo

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

《HDOJ 1171 Big Event in HDU》有33个想法

  1. 非常奇怪.最后的求解
    我是
    for(int i=sum/2;i<=sum;i++)
    {
    if(c1[i])
    {
    printf("%d %d\n",i,sum-i);
    break;
    }
    }
    这样从小到大的,最后是wa.而改成你的 从大往小,就没问题….

      1. Mr.Woo and 一口同学,
        请问这是为什么呢?sum/2不是sum的一半吗?难道是因为int相处的精度问题?求详解…拜托了。。
        如果单独分出来就能过,
        if(c1[sum/2]!=0)
        printf(“%d %d\n”,sum-sum/2,sum/2);//【AC】

        1. 如果改成

          printf(“%d %d\n”,um/2,sum/2) 或者

          printf(“%d %d\n”,sum/2,sum-sum/2)

          就Wrong了.为什么呢??!!

        2. 【?】AC完整的:
          if(c1[sum/2]!=0) printf(“%d %d\n”,sum-sum/2,sum/2);
          else
          {
          for(i=sum/2;i<=sum;i++)//向后搜索
          {
          if(c1[i]!=0)
          {
          break;
          }
          }
          printf("%d %d\n",i,sum-i);
          }

        3. Mr.Woo,
          这个WP Anti Spam的过滤好严格额。。
          字数稍微长一点就评论不了。。
          交流起来有点小累啊OO、

        4. 嗯,谢谢,,这个明白了。。
          可是向小的方向遍历为什么就不用考虑这些情况呢?

        5. 额,我大概明白了。如果说错了,希望前辈们指正哦。。

          int的整除中,sum/2如果刚好除尽则没有误差。但是如果只要没有”除尽”,误差带来的影响就是使它远离实际值而小的方向缩减。

        6. 所以,如果我们往增长的方向遍历就会把误差多考虑一次而导致加上的是错误(不存在)的变量的指数。

        7. 但是,如果我们往递减的方向遍历就不会重叠误差而导致影响的那个”点”(真实值),也就不用单独考虑sum/2是否刚好整除了。

          不知道表述清楚没。。

  2. for(int i= sum/2; i>=0; –i)
    if(c1[i] != 0)
    {
    printf(“%d %d\n”, sum-i, i);
    break;
    }
    1.为什么c[i]有 c[sum-i]就一定有?
    2.不是分堆吗 ,怎么保证c【i】里面使用的方案,c【sum-i】不会使用啊?

  3. 这份代码有bug。
    如果是开成bool数组的话没有问题,但是这里int数组里记录的是它的组合数,在这道题中会溢出。由于最后判断时用了c1[i] != 0,如果你改成>0的话结果会是错误的,只是因为刚好没有溢出到结果为0所以AC了而已。

  4. 刚才贴的代码有问题。。奇怪了。。我重新敲了一遍
    #include
    using namespace std;
    int f[250000];
    int aver;
    int value[55],amount[55];
    inline int getMax(int a,int b)
    {
    return a>b?a:b;
    }
    void ZeroOnePack(int w,int v)
    {
    for(int j=aver;j>=w;j–)
    {
    f[j]=getMax(f[j],f[j-w]+v);
    }
    }
    void CompletePack(int w,int v)
    {
    for(int j=w;j=aver)
    {
    CompletePack(w,v);
    return ;
    }
    int k=1;
    while(k<num)
    {
    ZeroOnePack(k*w,k*v);
    num-=k;
    k<0)
    {
    sum=0;
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d",&value[i],&amount[i]);
    sum+=value[i]*amount[i];
    }
    aver=sum/2;
    memset(f,0,sizeof(*f)*(aver+1));
    for(int i=1;i<=n;i++)
    MultiplyPack(value[i],value[i],amount[i]);
    int _Max=f[aver];
    if(_Max<sum-_Max)_Max=sum-_Max;
    printf("%d %d\n",_Max,sum-_Max);
    }

    return 0;
    }

  5. 刚刚看了另外的解法,这个题也可当作多重背包来做的。而且,多重背包时间更短一些。

    附另解:
    #include

    02 #include

    03 #include

    04

    05 #define MAXN 55

    06 #define MAXM 250001

    07

    08 int aver, value[MAXN], num[MAXN];

    09 int f[MAXM];

    10

    11 inline int getMax(int a, int b)

    12 {

    13 return a > b ? a : b;

    14 }

    15

    16 void ZeroOnePack(int w, int v)

    17 {

    18 for(int j = aver; j >= w; j–)

    19 {

    20 f[j] = getMax(f[j], f[j – w] + v);

    21 }

    22 }

    23 void CompletePack(int w, int v)

    24 {

    25 for(int j = w; j = aver)

    33 {

    34 CompletePack(w, v);

    35 return;

    36 }

    37 int k = 1;

    38 while(k < amount)

    39 {

    40 ZeroOnePack(k * w, k * v);

    41 amount -= k;

    42 k < 0)

    54 {

    55 int i = 0, sum = 0;

    56 for(i = 1; i > 1;

    62 memset(f, 0, sizeof(*f) * (aver + 1));

    63 for(i = 1; i <= n; i++) MultiplePack(value[i], value[i], num[i]);

    64 int theMax = f[aver];

    65 if(theMax < sum – theMax) theMax = sum – theMax;

    66 printf("%d %d\n", theMax, sum – theMax);

    67 }

    68 return 0;

    69 }

  6. 1085我算是看懂了,这个题目,类似的题目我见到过好多!
    都是要求分堆,要求两边差值最小,都是见一次不会一次,
    求教楼主,能把
    for(int i=0; i<=value[1]*amount[1]; i+=value[1])
    c1[i] = 1;
    int len = value[1]*amount[1];
    for(int i=2; i<=nNum; ++i)
    {
    for(int j=0; j<=len; ++j)
    for(int k=0; k<=value[i]*amount[i]; k+=value[i])
    {
    c2[k+j] += c1[j];
    }
    len += value[i]*amount[i];
    for(int j=0; j=0; –i)
    if(c1[i] != 0)
    {
    printf(“%d %d\n”, sum-i, i);
    break;
    }

    这一段注释一下么?
    感谢LZ啦!

发表评论

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