CodeForces 799C
题意： n 个温泉，有 C 个金币， D 枚钻石。现在要建两个温泉，每个温泉有一个价值，还有价格，但价格只是一种类型，即是用金币或钻石，也就是说每个温泉只能单独用金币或钻石。要在已有金币和钻石内，建两个温泉，求最后的最大价值。
tags： 处理出前缀，即花费 i 时可以得到的最大价值和次大价值。 然后枚举即可。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second #define PII pair<ll , ll > typedef long long ll; const int N = 100005;int n; ll C, D; PII c[N], d[N]; ll ans1[N][2], ans2[N][2]; int cnt1=0, cnt2=0; void Init() {sort(c+1, c+1+cnt1);sort(d+1, d+1+cnt2);ll mx1=0, mx2=0;rep(i,1,cnt1){if(mx1 < c[i].se){mx2=mx1, mx1=c[i].se;ans1[c[i].fi][0]=mx1;ans1[c[i].fi][1]=mx2;}else if(mx2 < c[i].se){mx2=c[i].se;ans1[c[i].fi][0]=mx1;ans1[c[i].fi][1]=mx2;}}mx1=0, mx2=0;rep(i,1,cnt2){if(mx1 < d[i].se){mx2=mx1, mx1=d[i].se;ans2[d[i].fi][0]=mx1;ans2[d[i].fi][1]=mx2;}else if(mx2 < d[i].se){mx2=d[i].se;ans2[d[i].fi][0]=mx1;ans2[d[i].fi][1]=mx2;}}rep(i,1,max(C,D)) rep(j,0,1){ans1[i][j]=max(ans1[i][j], ans1[i-1][j]);ans2[i][j]=max(ans2[i][j], ans2[i-1][j]);} } int main() {scanf("%d%lld%lld", &n, &C, &D);ll bi, pi; char ch;rep(i,1,n){scanf("%lld%lld%*c%c", &bi, &pi, &ch);if(ch=='C') c[++cnt1]=MP(pi, bi);else d[++cnt2]=MP(pi, bi);}Init();ll sum1=0;if(ans1[C][0] && ans2[D][0])sum1 = max(sum1, ans1[C][0]+ans2[D][0]);ll sum2=0, sum3=0;rep(i,1,cnt1){ll ret=C-c[i].fi;if(ret>0){if(ans1[ret][0]==c[i].se){if(ans1[ret][1])sum2 = max(sum2, c[i].se+ans1[ret][1]);}else{if(ans1[ret][0])sum2 = max(sum2, c[i].se+ans1[ret][0]);}}}rep(i,1,cnt2){ll ret=D-d[i].fi;if(ret>0){if(ans2[ret][0]==d[i].se){if(ans2[ret][1])sum3 = max(sum3, d[i].se+ans2[ret][1]);}else{if(ans2[ret][0])sum3 = max(sum3, d[i].se+ans2[ret][0]);}}}printf("%lld\n", max(sum1, max(sum2, sum3)));return 0; }
