题解 P2663 越越的组队
966123anyunchuan
·
·
题解
这道题是个背包类型的动态规划，但要求选出的人数正好是总人数的一半，普通01背包的状态并不能保证，于是在状态上再添加一维。
定义 f[i][j][k] 为在前 i 个人中选出正好 j 人正好装满容积为 k 的背包所获得的最大成绩。考虑第 i 个人选不选，得到转移方程：
因为定义的状态是正好装满的，所以最后还要枚举一下容积。
然后降维，得到如下AC代码：
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[110], sum, f[110][5010], ans;
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
sum+=a[i];
}
for(int i=1; i<=n; i++)
{
for(int j=i; j>=1; j--)
{
for(int k=sum/2; k>=a[i]; k--)
{
f[j][k]=max(f[j][k], f[j-1][k-a[i]]+a[i]);
}
}
}
for(int i=0; i<=sum/2; i++)
{
ans=max(ans, f[n/2][i]);
}
cout<<ans;
return 0;
}
```
大概是题解区里的一个新做法，~~有可能有锅~~。