首页 > 代码库 > bzoj1334 [Baltic2008]Elect
bzoj1334 [Baltic2008]Elect
Description
N个政党要组成一个联合内阁,每个党都有自己的席位数. 现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好. 对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的.
Input
第一行给出有多少个政党.其值小于等于300 下面给出每个政党的席位数.总席位数小于等于 100000
Output
你的组阁方案中最多能占多少个席位.
Sample Input
4
1 3 2 4
1 3 2 4
Sample Output
7
HINT
选择第二个政党和第四个
我又开始刷起水题了……
按a[i]从大到小排序,然后背包dp
某一政党退出后席位小等于总数的一半,就是要从j<=s/2的f[j]转移而来
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}int n,s;int a[500];bool f[100010];int main(){ n=read(); for (int i=1;i<=n;i++)a[i]=read(),s+=a[i]; sort(a+1,a+n+1,greater<int>()); f[0]=1; for (int i=1;i<=n;i++) { for (int j=100000;j>=a[i];j--) if (j-a[i]<=s/2) { f[j]=f[j]|f[j-a[i]]; } } for (int i=100000;i>=0;i--) { if (f[i]) { printf("%d\n",i); return 0; } }}
bzoj1334 [Baltic2008]Elect
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。