首页 > 代码库 > bzoj1334 [Baltic2008]Elect

bzoj1334 [Baltic2008]Elect

2024-08-08 08:02:39   222人阅读

Description

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

Input

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

Output

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

Sample Input

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


联系
我们