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

题目描述

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002.

The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

思路

依旧是母函数:
$$G x=\left(1+x^{V_1}+x^{V_1 2}+\dots+x^{V_1 M_1}\right) \left(1+x^{V_2}+x^{V_2 2}+\dots+x^{V_2 M_2}\right)\left(1+x^{V_N}+x^{V_N 2}+\dots+x^{V_N M_N}\right)$$

展开后,从中间项往一边搜索即可。

这里有陷阱,因为组合数太大会溢出,所以不能用判断系数$>0$,WA了十几次。。

AC代码

/*************************************************************************
    > File Name: 1171.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-03 Fri 20:08:52 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max = 250000;
struct fac {
    int V, M;
} fac[51]; // 设施属性

int main()
{
#ifdef Oj
    freopen("1171.in", "r", stdin);
#endif
    static int c1[_max], c2[_max]; // c1为展开后的系数,c2为每一个表达式的中间系数
    int N;
    while(cin >> N && N>0) { // 题目有点坑,不是$N==-1$退出,而是$>0$
        for (int i = 1; i <= N; ++i)
            cin >> fac[i].V >> fac[i].M;
        memset(c1, 0, sizeof(c1)); // 归零
        memset(c2, 0, sizeof(c2));
        int count = fac[1].V*fac[1].M; // 第一个表达式的最大设施价值
        for(int i=0; i<=count; i+=fac[1].V) // 步长应该是$+V_i$而不是+1
            c1[i] = 1; // 初始化为1

        for(int i=2; i<=N; ++i) { // 从第二个表达式开始
            count += fac[i].V*fac[i].M; // 每次增加的设施价值
            for(int j=0; j<=count; ++j) 
                for(int k=0;(j+k<=count) && ( k<=fac[i].V*fac[i].M); k+=fac[i].V) // 注意这里步长也是$+V_i$
                    c2[k+j] += c1[j]; // 合并
            for(int j=0; j<=count; ++j) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }

        for(int i=count/2; i<=count; ++i)  // 从中间开始往后,也可以往前搜索
            if(c1[i] != 0) { // 这里有陷阱,因为组合数太大会溢出,所以不能用判断$>0$,WA了十几次。。
                printf("%d %d\n", max(i, count-i),min(i,count-i));
                break;
            }
    }
    return 0;
}