加权就可以用dp
by ix35 @ 2019-12-01 18:55:21
为什么要树状数组
by yummy @ 2019-12-01 19:00:06
@[yummy](/user/101694) 求区间最大值
by xingzi @ 2019-12-01 19:55:56
~~调了20分钟~~随手写了个树状数组优化：
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int f[100010],tt[100010];
int n;
struct competition{
int st,en,w;
}c[100010];
int lowbit(int x){
return x&(-x);
}
void update(int x,int y){
for(; x<=n; x+=lowbit(x)){
if(y>tt[x])
tt[x]=y;
else
break;
}
}
int getmax(int x,int y){
int ans=-1;
for(; y>=x; y-=lowbit(y)){
ans=max(ans,tt[y]);
if(y==0) break;//%%%死循环警告
}
return ans;
}
bool cmp(const competition &a,const competition &b){
return a.en<b.en;
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d%d%d",&c[i].st,&c[i].en,&c[i].w);
}
sort(c+1,c+n+1,cmp);
for(int i=1; i<=n; i++){//枚举每一场比赛
int y=-1;
for(int j=i-1; j>=1; j--){
if(c[j].en<=c[i].st){
y=j;
break;
}
}
if(y>=0){
f[i]=getmax(0,y)+c[i].w;
}
else f[i]=c[i].w;
//for(int j=i; j<=y; j++)
update(i,f[i]);
//printf("f[%d]:%d\n",i,f[i]);
}
int maxx=0;
for(int i=1; i<=n; i++){
//printf("%d:%d\n",i,f[i]);
maxx=max(maxx,f[i]);
}
printf("%d\n",maxx);
//int time=-1;
//for(int i=1; i<=n; i++){
// if(time<=c[i].st){
// time=c[i].en;
// cnt++;
// }
//}
return 0;
}
/*
4
0 2 1
1 3 1
2 4 2
0 1 2
*/
```
by xingzi @ 2019-12-01 19:59:57
@[xingzi](/user/134884) 单调队列不香吗
by yummy @ 2019-12-01 20:00:00
@[yummy](/user/101694) ~~我菜死了不会写单调队列优化~~
by xingzi @ 2019-12-01 20:12:10