HDU 1171.Big Event in HDU

162

题目



Description  


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).



Input  


Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0<V<=50 --value of facility) and an integer M (0<M<=100 --corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.


Output  


For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.


Sample Input  


2
10 1
20 1
3
10 1
20 2
30 1
-1


Sample Output  


20 10
40 40


翻译


背景


我们知道现在计算机学院是 HDU 最大的院系,但是你可能不知道在2002年,计算机学院被分为计算机学院和软件学院两个院系
这次院系分离是 HDU 的大事,同时它还导致了许多问题
许多东西都要分成两份
首先,所有设施已经被评估过,如果两个设施的值不同,那么就被看作两个不同的设施
所有设施被分为 N 个种类( 0<N<1000 )

>

输入


输入包括多组数据
每组数据开始有一个整数 N ( 0<N<=50 ) ,表示设施种类的数目
接下来 N 行每行有一个值 V ( 0<V<=50 ),表示设施的编号
一个整数 M ( 0<M<=100 ),表示设施的数目
N 为负数时表示输入结束

>

输出


对于每组数据,在一行内输出两个整数 AB
分别表示计算机学院和软件学院的设施数目,两个数应该尽可能相等,并且 A 不少于 B


题解


题目要求就是对东西进行平均分配
如果一个东西有偶数个,那么直接除以 2 就是最好的分配方案
然而对于
5 2
10 1


最优解是把值为 5 的分给一个人

可以感受到背包问题

使用 dp[i][j] 记录在不大于遍历到设施 i 同时已经得到的设施总数为 j 的情况下的最大值
其中, j 小于等于所有设施总数的一半

那么……这不就是 **>多重背包问题<**

魔改了好久背包问题,最好发现就是模板……
求心理阴影面积

最后从所有设施总数的一半往小筛选,第一个不是 0 的就是软件学院的设施数,总数减去它就是计算机学院的设施数

数据范围有点迷,一会 | acc312284ff2e12440175c114174f3c934 | 一会 | acc312284ff2e12440175c114174f3c935 | 往大的开吧

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 1000;
const int maxv = 300000;
const int INF = 0x7fffffff;
int dp[maxv];
int value[maxn],num[maxn];
int Max;
int v;

void ZeroOnePack(int cost,int weight) {
    for(int i = v; i >= cost; i--)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}
void CompletePack(int cost,int weight) {
    for(int i = cost; i <= v; i++)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}
void MultiplePack(int cost,int weight,int n) {
    if(cost * n > v) {
        CompletePack(cost,weight);
    } else {
        int k = 1;
        while(k < n) {
            ZeroOnePack(cost * k,weight * k);
            n -= k;
            k *= 2;
        }
        ZeroOnePack(cost * n,weight * n);
    }
}

bool  Do() {
    int n;
    scanf("%d",&n);
    if(n < 0)
        return false;

    Max = 0;

    for(int i = 1;i <= n;i++) {
        scanf("%d%d",&value[i],&num[i]);
        Max += value[i] * num[i];
    }

    v = Max / 2;
    memset(dp,0,sizeof(dp));

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

    int ans = 0;
    for(int i = v;i >= 0;i--) {
        if(dp[i] != 0) {
            ans = dp[i];
            break;
        }
    }

    printf("%d %d\n",Max - ans,ans);
    return true;
}

int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论