首页 > 代码库 > HDU 1171 Big Event in HDU --暴力+生成函数

HDU 1171 Big Event in HDU --暴力+生成函数

2024-07-04 12:17:35   235人阅读

题意：给n种房子，每种房子有一个值val和个数cnt，现在要把这些房子分成两部分，争取两部分总值相等，如果不能相等，让A>B,且A-B最小。

解法：先跑一次生成函数，c[n]表示组成总值为n的方法种数，然后从Total/2~0枚举B的总值，如果c[i]不为0，说明可以达到 i 这个状态，说明这就是B的最接近A的值（因为最接近Total/2）。算法复杂度较高。跑了1600多ms，不知道还有没有更优的算法。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 250007

int c[N],tc[N];

int main()
{
    int val[55],num[55];
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF && n > 0)
    {
        int maxi = 0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&val[i],&num[i]);
            maxi += val[i]*num[i];
        }
        for(i=0;i<=maxi;i++)
            c[i] = tc[i] = 0;
        for(i=0;i<=val[0]*num[0];i+=val[0])
            c[i] = 1;
        for(i=1;i<n;i++)
        {
            for(j=0;j<=maxi;j++)
            {
                for(k=0;k+j<=maxi && k<=val[i]*num[i];k+=val[i])
                    tc[k+j] += c[j];
            }
            for(j=0;j<=maxi;j++)
            {
                c[j] = tc[j];
                tc[j] = 0;
            }
        }
        for(i=maxi/2;i>=0;i--)
            if(c[i])
                break;
        printf("%d %d\n",maxi-i,i);
    }
    return 0;
}
View Code

 


联系
我们