pts60
\(dp[i][j][k]\) 表示前 \(i\) 个士兵 \(j\) 个弓箭手 \(k\) 个步兵
\(dp[i][j][k]=max(dp[i-1][j-1][k]+a[i],dp[i][j][k]);\)
\(dp[i][j][k]=max(dp[i-1][j][k-1]+b[i],dp[i][j][k]);\)
pts100
先按照 \(a\) 排序 观察有什么美好的性质
在答案中标出 \(b\) 的位置,发现 \(a\) 是从左往右选的
那么模拟此过程
\(~~~\) 记录最后一个位置是 \(i\) ,那么前 i 个位置里,有 \(A\) 个 \(a\),有 \(i-A\) 个 \(b\) \((step1)\)
\(~~~\) 再在 \(i~n\) 里面选 \(A+B-i\) 个 \(b\) 即可 \((step2)\)
step2
对于 \(step2\) 中,确定的 \(i\) 对应结果是确定的
因此可以预处理出 \(suf[i]\) 表示 枚举的是 \(i\) 时的 \(step2\) 的贡献
step1
detail1:
当第 \(A+1\) 个数以后,需要决策当前是选 a 还是选 b , 并可能要替代已选的 a 中间的某个值
替代所改变的价值表现为 : \(-a[j] + b[j] + a[i]\)
为了直接调用 \(-a[j] + b[j]\) 最大 直接用优先队列维护
比较价值 : \(a[i]+q.top()+suf[i+1]\) (作为 \(a\)) \(b[i]+suf[i+1]\) (作为 \(b\))
detail2:
排序 \(a\) 相同时 \(b\) 大的排前面
整体上类似于一个带反悔的贪心
AC代码奉上
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int A,B,n;
struct P{
int a,b;
bool friend operator <(P x,P y){
if(x.a==y.a)return x.b>y.b;
return x.a>y.a;
}
}p[N];
namespace pts60{
int dp[105][105][105];
void solve(){
dp[0][0][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=A;++j){
for(int k=0;k<=B;++k){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
if(j)dp[i][j][k]=max(dp[i-1][j-1][k]+p[i].a,dp[i][j][k]);
if(k)dp[i][j][k]=max(dp[i-1][j][k-1]+p[i].b,dp[i][j][k]);
}
}
}
printf("%d",dp[n][A][B]);
}
}
namespace full_mark{
priority_queue<int> q;
int suf[N],now=0;
void previous(){
sort(p+1,p+n+1);
for(int i=A+B+1;i<=n;++i)q.push(p[i].b);
}
void init_suf(){
for(int i=A+B;i>A;--i){
q.push(p[i].b);
suf[i]=suf[i+1]+q.top();
q.pop();//注意pop
}
while(!q.empty())q.pop();
for(int i=1;i<=A;++i){
now+=p[i].a;
q.push(p[i].b-p[i].a);
}
}
void solve(){
previous();
init_suf();
int ans=now+suf[A+1];
for(int i=A+1;i<=A+B;++i){
if(q.top()+p[i].a<p[i].b){
now+=p[i].b;
continue;
}
now+=q.top()+p[i].a;
q.push(p[i].b-p[i].a);
ans=max(ans,now+suf[i+1]);
q.pop();//注意pop
}
printf("%d",ans);
}
}
int main(){
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;++i)scanf("%d",&p[i].a);
for(int i=1;i<=n;++i)scanf("%d",&p[i].b);
return full_mark::solve(),0;
}