分几种情况讨论:

(1)仅用C或D买两个

  ①买两个代价相同的(实际不同)(排个序)

  ②买两个代价不同的(因为买两个代价相同的情况已经考虑过了,所以此时对于同一个代价,只需要保存美丽度最高的喷泉即可)(预处理b[i],表示代价小于等于i的物品中,美丽度最大的是多少。为了防止重复购买,枚举其中一个,然后另一个只买代价小于其代价的物品。)

(2)用C和D各买一个

按这几种情况分类,可以比较好地避免买到同一个喷泉的情况。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,c,d,b[100010],p[100010];
char op[100010][3];
struct data{
int v,c;
}a1[100010],a2[100010];
int b1[100010],b2[100010];
bool operator < (const data &a,const data &b){
return a.c!=b.c ? a.c<b.c : a.v<b.v;
}
int ans=0;
int main(){
// freopen("c.in","r",stdin);
scanf("%d%d%d",&n,&c,&d);
int m1=0,m2=0;
for(int i=1;i<=n;++i){
scanf("%d%d%s",&b[i],&p[i],op[i]);
if(op[i][0]=='C'){
a1[++m1]=(data){b[i],p[i]};
}
else{
a2[++m2]=(data){b[i],p[i]};
}
}
sort(a1+1,a1+m1+1);
for(int i=2;i<=m1;++i){
if(a1[i].c==a1[i-1].c && a1[i].c*2<=c){
ans=max(ans,a1[i].v+a1[i-1].v);
}
}
for(int i=1;i<=m1;++i){
b1[a1[i].c]=max(b1[a1[i].c],a1[i].v);
}
for(int i=1;i<=c;++i){
b1[i]=max(b1[i],b1[i-1]);
}
for(int i=1;i<=m1;++i){
if(a1[i].c<=c && b1[min(c-a1[i].c,a1[i].c)-(a1[i].c<=c-a1[i].c)]){
ans=max(ans,a1[i].v+b1[min(c-a1[i].c,a1[i].c)-(a1[i].c<=c-a1[i].c)]);
}
} sort(a2+1,a2+m2+1);
for(int i=2;i<=m2;++i){
if(a2[i].c==a2[i-1].c && a2[i].c*2<=d){
ans=max(ans,a2[i].v+a2[i-1].v);
}
}
for(int i=1;i<=m2;++i){
b2[a2[i].c]=max(b2[a2[i].c],a2[i].v);
}
for(int i=1;i<=d;++i){
b2[i]=max(b2[i],b2[i-1]);
}
for(int i=1;i<=m2;++i){
if(a2[i].c<=d && b2[min(d-a2[i].c,a2[i].c)-(a2[i].c<=d-a2[i].c)]){
ans=max(ans,a2[i].v+b2[min(d-a2[i].c,a2[i].c)-(a2[i].c<=d-a2[i].c)]);
}
} if(b1[c] && b2[d]){
ans=max(ans,b1[c]+b2[d]);
} printf("%d\n",ans);
return 0;
}
05-23 01:22