题解 AT3857 【Median Sum】

紫题

2018-10-23 11:02:23

Solution

01背包的思想+bitset优化 设$f[i][j]$为用前i个数,能否组成数字$j$ $(f[i][j]∈{0,1})$ 转移:$f[i][j]=(f[i-1][j-a[i]])|(f[i-1][j])$ 省去第一维,再用bitset进行整体的转移 再看中位数的选取 设所有数的总和为$sum$,如果$f[x]=1$,那一定有$f[s-x]=1$ 所以$f[]$是对称的 直接从$sum/2$开始扫即可 ```cpp #include<iostream> #include<bitset> using namespace std; int n,x,sum; bitset<2000007>f; int main(){ cin>>n; f[0]=1; for(int i=1;i<=n;i++){ cin>>x; f|=f<<x; sum+=x; } for(int i=(sum+1)/2;i<=sum;i++){ if(f[i]) {cout<<i<<endl;break;} } return 0; } ```