首页 > 代码库 > 【预处理】【分类讨论】Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains
【预处理】【分类讨论】Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains
分几种情况讨论：
（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;
}
【预处理】【分类讨论】Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。