【题目大意】
给定n个物品，第i个物品有三个属性Ai,Bi,Ci。然后把这个n个物品分别分到3个集合中（集合可以为空），使得A集合中的物品的Max{Ai}+B集合中的物品的Max{Bi}+C集合中物品的Max{Ci}最小。（空集算作0）
【算法分析】
HDOJ3552是只有两个属性，那么按Ai排序，然后枚举Max{Ai}。然后剩下的另一边的Max{Bi}加起来就是当前值。
然后对于本题。依然按Ai排序，仍然从大到小枚举Max{Ai}。然后对剩下的另一边维护上面那个问题。
显然，若存在Bi<=Bj Ci<=Cj，那么i这个物品就没用了。那么我们可以维护一个线性表，使得他关于Bi递增。同时，删掉多余的物品以后，关于Ci递减。那么很显然，我们取某一个物品截开，那么这边取的值就是Bi+Ci+1，然后这种动态线性表显然就可以用平衡树维护。然后为了比较方便找前驱和后继，我用了Splay。
【其它】1Y。这次把Splay函数和rotate函数压了代码，Splay只有两个rotate，rotate里不用分类讨论。
【CODE】
#include #include #include #include #include using namespace std; const int N=105555; const int INF=1000000000; int n,root; struct Node{int x,y,z;}a[N]; int pre[N],best[N],w[N],ch[N][2]; bool cmp(const Node &A,const Node &B){ return A.x } void init(){ int i; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+n+1,cmp); memset(ch,0,sizeof(ch)); memset(pre,0,sizeof(pre)); root=n+1; ch[n+1][0]=n+2; pre[n+2]=n+1; a[n+1].y=INF; a[n+1].z=0; a[n+2].y= 0; a[n+2].z=INF; w[n+1]=INF; best[n+1]=0; w[n+2]=best[n+2]=0; } void update(int x){ best[x]=INF; if (ch[x][0]) best[x]=min(best[ch[x][0]],best[x]); if (ch[x][1]) best[x]=min(best[ch[x][1]],best[x]); best[x]=min(w[x],best[x]); } void rotate(int x,int T){ int y=pre[x]; ch[y][!T]=ch[x][T]; ch[x][T]=y; pre[x]=pre[y]; pre[y]=x; pre[ch[y][!T]]=y; if (ch[pre[x]][0]==y) ch[pre[x]][0]=x; else ch[pre[x]][1]=x; update(y); update(x); } void Splay(int x,int goal){ int y,z; if (x==0 || x==goal) return; if (goal==0) root=x; while (pre[x]!=goal){ y=pre[x]; z=pre[y]; if (z!=goal) rotate(ch[z][0]==y^ch[y][0]==x?x:y,ch[y][0]==x); rotate(x,ch[pre[x]][0]==x); } }
void Get_next(){
int p=ch[root][1],q=root;
while (p){
q=p;
p=ch[p][0];
}
Splay(q,0);
}
void Get_pre(){
int p=ch[root][0],q=root;
while (p){
q=p;
p=ch[p][1];
}
Splay(q,0);
}
bool Can_Insert(int i){
int p=root,q;
while (p){
q=p;
p=ch[p][a[p].y } Splay(q,0); if (a[q].y if (a[root].y>=a[i].y && a[root].z>=a[i].z) return false; else return true; } void (){ int p=ch[root][0]; while (ch[p][1]) p=ch[p][1]; Splay(p,root); ch[p][1]=ch[root][1]; pre[ch[root][1]]=p; pre[p]=0; root=p; }
void Delete_Useless_Node(int i){
while (1){
if (a[root].y>a[i].y) Get_pre();
if (a[root].y<=a[i].y && a[root].z<=a[i].z)
();
else
break;
}
}
void Insert(int i){
int p=root,q;
while (p){
q=p;
p=ch[p][a[p].y } pre[i]=q; ch[q][a[q].y Splay(i,0); p=ch[i][1]; while (ch[p][0]) p=ch[p][0]; w[i]=a[i].y+a[p].z; Splay(p,i); update(i); Get_pre(); w[root]=a[root].y+a[i].z; update(root); } void Try_Insert(int i){ if (!Can_Insert(i)) return; Delete_Useless_Node(i); Insert(i); } void work(){ int i,ans=INF,now; a[0].x=0; for (i=n;i>=0;i–){ now=a[i].x; now+=best[root]; if (now Try_Insert(i); } printf("%dn",ans); } int main(){ init(); work(); return 0; }