1334: [Baltic2008]Elect

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?575??Solved:?333
[Submit][Status][Discuss]

Description

N個政黨要組成一個聯合內閣，每個黨都有自己的席位數. 現在希望你找出一種方案，你選中的黨的席位數要大于總數的一半，并且聯合內閣的席位數越多越好. 對于一個聯合內閣，如果某個政黨退出后，其它黨的席位仍大于總數的一半，則這個政黨被稱為是多余的，這是不允許的.

Input

第一行給出有多少個政黨.其值小于等于300 下面給出每個政黨的席位數.總席位數小于等于 100000

Output

你的組閣方案中最多能占多少個席位.

Sample Input

4
1 3 2 4

Sample Output

7

HINT

選擇第二個政黨和第四個

?

#include <cstdio> #include <algorithm>using namespace std;int a[301],f[100001]; int main() {int n,i,j,sum = 0,ans = 0;scanf("%d" , &n);for(i = 1 ; i <= n ; i ++ )scanf("%d" , &a[i]) , sum += a[i];sort(a + 1 , a + n + 1);f[0] = 1;for(i = n ; i >= 1 ; i -- )for(j = sum / 2 + a[i] ; j >= a[i] ; j -- )if(f[j - a[i]])f[j] = 1 , ans = max(ans , j);printf("%d\n" , ans);return 0; }

?

轉載于:https://www.cnblogs.com/L-Memory/p/7061645.html

總結

以上是生活随笔為你收集整理的bzoj1334[Baltic2008]Elect(背包dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。