目录

  1. 引言
  2. BZOJ 1334: [Baltic2008]Elect
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 1334: [Baltic2008]Elect 题解

BZOJ 1334: [Baltic2008]Elect

  • Time Limit: 10 Sec

  • Memory Limit: 162 MB

Description

N个政党要组成一个联合内阁,每个党都有自己的席位数. 现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好. 对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的.

Input

第一行给出有多少个政党.其值小于等于300 下面给出每个政党的席位数.总席位数小于等于 100000

Output

你的组阁方案中最多能占多少个席位.

Sample Input

4

1 3 2 4

Sample Output

7

HINT

选择第二个政党和第四个

题目分析

十分简单的背包DP

每次只使用容量不超过一半的状态来转移

代码

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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define maxn 200005
#define ll long long int
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '0') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m = 0;
bool dp[maxn];
int g[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("elect.in", "r", stdin);
#endif
ll sum = 0;
read(n);
rep(i, 1, n) read(g[i]), m += g[i];
sort(g + 1, g + 1 + n);
dp[0] = 1;
int mid = m >> 1;
per(i, n, 1) per(j, min(g[i] + mid, m), g[i]) dp[j] |= dp[j - g[i]];
per(i, m, 0) if (dp[i]) {
printf("%d", i);
return 0;
}
assert(false);
return 0;
}