首页 > 其他 > 详细

LUOGU P4394 [BOI2008]Elect 选举 (背包)

时间:2018-10-15 16:57:55      阅读:36      评论:0      收藏:0      [点我收藏+]

标签:problem   .org   names   algorithm   tdi   ring   tps   --   for   

传送门

解题思路

  一眼看上去就像个背包,然后就是\(0/1\)背包改一改,结果发现过不了样例。后来想了一下发现要按\(a\)从大到小排序,因为如果对于一个>=总和的一半但不满足的情况来说,把最小的去掉也一定>=总和的一半。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;
const int MAXN = 305;

inline int rd(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}
    return x;
} 

int n,f[MAXN][100005],a[MAXN],Sum;
 
inline bool cmp(int x,int y){
    return x>y;
} 
 
int main(){
    n=rd();
    for(int i=1;i<=n;i++) a[i]=rd(),Sum+=a[i];
    sort(a+1,a+1+n,cmp);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=Sum;j++){
            f[i][j]|=f[i-1][j];
            if(j>=a[i] && j-a[i]<=Sum/2) f[i][j]|=f[i-1][j-a[i]]; 
        }
    for(int i=Sum;i;i--) 
        if(f[n][i]) {printf("%d",i);return 0;}
}

LUOGU P4394 [BOI2008]Elect 选举 (背包)

标签:problem   .org   names   algorithm   tdi   ring   tps   --   for   

原文:https://www.cnblogs.com/sdfzsyq/p/9791912.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号