P9814 [CCC 2015 S5] Greedy For Pies 题解
__zfy__
·
·
题解
思路
第一眼贪心，证明的时候自己设了一个大样例，输出错了，发现这题局部选择 b_i 并不能使 b 这个序列最优。
考虑 DP，先看 b 数组，它的使用只有两个：辅助我们选 a 的两个数，选它自己的数。在贪心做法中，最大的总是作为被选的，而小一些的数往往是辅助选 a 的数的。
如果考虑 DP，那首先就要定义 dp_i 的状态，\mathit{dp}_{i,j,k,*} 为第 i 个 a_i 前面的数和已经选的第 j 个 b_j 前面的数，其中有 k 个不是用来辅助的数。
如让 b 升序选，b_i 当辅助的数，0，1 的转移分别为：\mathit{dp}_{i,j,k,0} = \max(\mathit{dp}_{i-1,j,k,0},\mathit{dp}_{i-1,j,k,1})
如果 $b$ 升序，不选 $b_i$ 当辅助的数，不辅助的和辅助的的转移分别为：
$\mathit{dp}_{i,j,k,0} = \max(\mathit{dp}_{i,j,k,0},\mathit{dp}_{i-1,j-1,k-1,0},\mathit{b}_{m-k+1})
空间问题，要开 `vector`，不然 MLE，总复杂度不会超时，大约为 $O(nm^2)$ 左右。
### 代码
来自[TA](https://www.luogu.com.cn/user/295398)。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e3+10;
int n,m,ans,a[N],b[105],f[2][105][105][2];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
sort(b+1,b+m+1);
for(int i=1;i<=n;i++) {
int now=i&1,pre=now^1;
for(int j=0;j<=m;j++) {
for(int k=0;k<=j;k++) {
f[now][j][k][0]=max(f[pre][j][k][1],f[pre][j][k][0]);
f[now][j][k][1]=f[pre][j][k][0]+a[i];
if(j&&k) f[now][j][k][0]=max(f[now][j][k][0],f[pre][j-1][k-1][0]+b[m-k+1]);
if(j-1>=k) f[now][j][k][1]=max(f[now][j][k][1],f[pre][j-1][k][1]+a[i]);
ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
}
}
}
for(int i=n+1;i<=n+m;i++) {
int now=i&1,pre=now^1;
for(int j=0;j<=m;j++) {
for(int k=0;k<=j;k++) {
if(j) f[now][j][k][0]=max(f[pre][j-1][k][1],f[pre][j-1][k][0]);
if(j&&k) f[now][j][k][1]=f[pre][j-1][k-1][0]+b[m-k+1];
ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
}
}
}
cout<<ans<<"\n";
return 0;
}
```