HDOJ 1171 Big Event in HDU

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

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

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

 // Author: Tanky Woo
// HDOJ 1171


#include 
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;
}