题意： 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 ", max(sum1, max(sum2, sum3))); return 0; }