这题的关键在于注意到因为 $S$ 中包含了所有 $a$ 序列的子序列的和。那么假设其中一个集合的和为 $P$（包含 $0$），总和为 $Sum$，那么 $Sum-P$ 也一定在 $S$ 中，那么我们考虑将所有数排在数轴上，那么所有的点一定存在一个对称点，我们考虑算出中点坐标，即 $\frac{Sum}{2}$。也就是说，在考虑 $0$ 的情况下，答案就是 $\frac{Sum}{2}$。

现在把 $0$ 删去，那么中位数就会移动到靠后的那个点上。也就是说，答案就是最小的大于等于 $\frac{Sum}{2}$ 的能被凑出来的数。

考虑使用 dp 算出每个数能否被凑出来，然后扫一遍即可，但这样复杂度是 $O(n\times\sum_{i=1}^{n}{a_{i}})$ 的。显然无法通过。

我们发现最费时的时间在每一次转移时都要枚举总和然后一个个转移。所以考虑使用 bitset 优化。

最终代码：

#include<bits/stdc++.h>
using namespace std;
int a[2005];
bitset<4000005> dp;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		dp|=dp<<a[i];
	}
	int w=0;
	for(int i=1;i<=sum[n];i++){
		if(dp[i] && abs(w*2-sum[n])>=abs(i*2-sum[n])){
			w=i;
		}
	}
	cout<<w;
	return 0;
}

首先看到 $n$ 和 $A_i$ 最大只到2000，考虑背包。设 $f_i$ 表示 $i$ 是否在 $S$ 数列中出现过。

转移方程：$f[j]$ $|=$ $f[j-a[i]]$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000
int a[N+1];bool f[N*N+1];
signed main()
{
	int n;scanf("%lld",&n);int s=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];
	sort(a+1,a+n+1);f[0]=1;
	for(int i=1;i<=n;i++)for(int j=s;j>=a[i];j--)
		f[j]|=f[j-a[i]];
	for(int i=(s+1)/2;i<=N*N;i++)
		if(f[i]){printf("%lld\n",i);return 0;}
}

然而 $4e6$ 的常数有点大，让这份代码“只”拿了72分。 于是我们考虑优化。由于我们只要求中位数，所以求 $S$ 数列的后半部分就多余了。考虑将 $S$ 数列和 $0$ 放到数轴上，两边关于 $sum/2$ 这个点对称（$sum$ 为 $S$ 数列的和），答案为 $sum/2$ 这个点右边的第一个点。易得任意两点之间距离不超过2000，因此答案不会超过 $(sum/2+1000)$。

详见代码。

#include<bits/stdc++.h>
using namespace std;
#define N 2000
int a[N+1];bool f[N*N+1];
int main()
{
	int n;scanf("%d",&n);int s=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),s+=a[i];
	sort(a+1,a+n+1);s=(s+1)/2;f[0]=1;
	for(int i=1;i<=n;i++)for(int j=s+N/2;j>=a[i];j--)f[j]|=f[j-a[i]];
	for(int i=s;i<=s+N/2;i++)if(f[i]){printf("%d\n",i);return 0;}
}

于是我们拿到了最劣解，撒花~~~

阎帝的玄学方法

为什么最终的答案是$\frac{sum}{2}$各个题解已经解释过了，我就不过多赘述了。

这道题就转换为了这$a_i$个数进行01背包，但是直接暴力找会TLE（经duanjiahui实践发现第二重循环只需要循环到$2\times10^6$即可AC），所以我直接另开了一个$b$数组来记录目前有那些数可以得到，每次把$b$数组跑一遍即可。

玄学AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2100;
int a[N],n,b[N*N];
bool v[N*N];
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	int l=1;b[1]=0;
	for(int i=1;i<=n;i++)
	{
		int nl=l;
		for(int j=1;j<=nl;j++)
		{
			if(!v[b[j]+a[i]])b[++l]=b[j]+a[i],v[b[j]+a[i]]=1;
		}
	}
	sort(b+1,b+l+1);
//	for(int i=1;i<=l;i++)printf("%lld ",b[i]);puts("");
	printf("%lld\n",b[l/2+1]);
	return 0;
}

$S$中包含了所有$A$的非空子序列的和，所以对于每一个$S_i$，令$S$的总和为$Sum$，都有$S_j = Sum - S_i$。容易看出，$S$的中位数

#include<bits/stdc++.h>
using namespace std;
const int N = 2011;
typedef long long LL;
LL a[N], dp[N*N];
vector<int> sum;
int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sum.push_back(0); dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int siz = sum.size();
        for (int j = 0; j < siz; j++)
            if (!dp[sum[j] + a[i]])
                dp[sum[j] + a[i]] = 1, sum.push_back(sum[j] + a[i]);
    }
    sort(sum.begin(), sum.end());
    cout << sum[sum.size() / 2];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,x,sum;//sum是∑a[i] 
bitset<4000001>f;//这是STL中的二进制容器,可以参与运算
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	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;
}

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$开始扫即可

#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;
}