「BZOJ1334」[Baltic2008] Elect
Description
N个政党要组成一个联合内阁，每个党都有自己的席位数. 现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好. 对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.
Input
第一行给出有多少个政党.其值小于等于300 下面给出每个政党的席位数.总席位数小于等于 100000
Output
你的组阁方案中最多能占多少个席位.
Sample Input
4
1 3 2 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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<bitset> #include<cstring> #define ll long long #define inf 2000000000 #define mod 10000 using namespace std; inline int read() { int 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; } int n,sum,ans; int a[305]; int f[100005]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; sort(a+1,a+n+1,greater<int>()); f[0]=1; for(int i=1;i<=n;i++) for(int j=sum/2+a[i];j>=a[i];j--) { if(f[j-a[i]]) { f[j]=1; ans=max(j,ans); } } printf("%d",ans); return 0; } |
计数器 9824632
OI 课件=>
OI 课件=>
QAQ不用了已经知道了。。
求问为什么要排序
谢谢