http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2412
先dp出每个时刻的所能获得的最大分值，线段树维护每个时刻的最优值，对于i时刻，可以先求出区间1到i-m-1的最大值，然后更新i。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 #define maxn 10005 8 struct op{ 9 int t,val,pos; 10 }mes[maxn]; 11 struct node{ 12 int num; 13 }setree[maxn<<2]; 14 int dp[maxn],tmp[maxn]; 15 bool cmp(struct op a,struct op b) 16 { 17 if(a.t!=b.t) 18 return a.t<b.t; 19 return a.pos<b.pos; 20 } 21 int solve(int k) 22 { 23 int cnt=0; 24 if(tmp[0]==1) 25 cnt=1; 26 else 27 cnt=0; 28 int ans=tmp[0]; 29 for(int i=1;i<k;i++){ 30 if(tmp[i]==1){ 31 if(tmp[i-1]<=0) 32 tmp[i]=1; 33 else{ 34 if(cnt<2) 35 tmp[i]=tmp[i-1]+1; 36 else if(cnt==2) 37 tmp[i]=tmp[i-1]+4; 38 else 39 tmp[i]=tmp[i-1]+2; 40 } 41 cnt++; 42 } 43 else{ 44 cnt=0; 45 tmp[i]=max(tmp[i-1],0)-1; 46 } 47 ans=max(ans,tmp[i]); 48 } 49 return ans; 50 } 51 void cal(int n) 52 { 53 int k=0; 54 mes[n].t=maxn; 55 for(int i=0;i<=n;i++){ 56 if(i==0||mes[i].t==mes[i-1].t){ 57 tmp[k++]=mes[i].val; 58 } 59 else{ 60 dp[mes[i-1].t]=solve(k); 61 k=0; 62 tmp[k++]=mes[i].val; 63 } 64 } 65 } 66 void build(int l,int r,int rt) 67 { 68 setree[rt].num=0; 69 if(l==r) 70 return ; 71 int m=(l+r)>>1; 72 build(lson); 73 build(rson); 74 } 75 void pushup(int rt) 76 { 77 setree[rt].num=max(setree[rt<<1].num,setree[rt<<1|1].num); 78 } 79 void update(int l,int r,int rt,int num,int c) 80 { 81 if(l==r){ 82 setree[rt].num=c; 83 return; 84 } 85 int m=(l+r)>>1; 86 if(num<=m) 87 update(lson,num,c); 88 else 89 update(rson,num,c); 90 pushup(rt); 91 } 92 int query(int l,int r,int rt,int L,int R) 93 { 94 if(L>R) 95 return 0; 96 if(L<=l&&r<=R) 97 return setree[rt].num; 98 int m=(l+r)>>1; 99 int ans=0; 100 if(L<=m) 101 ans=max(ans,query(lson,L,R)); 102 if(R>m) 103 ans=max(ans,query(rson,L,R)); 104 return ans; 105 } 106 int main() 107 { 108 int t,cas=1; 109 scanf("%d",&t); 110 while(t--){ 111 int n,m,T=0; 112 memset(dp,0,sizeof(dp)); 113 scanf("%d%d",&n,&m); 114 for(int i=0;i<n;i++){ 115 int a; 116 scanf("%d%d%d",&mes[i].t,&a,&mes[i].pos); 117 T=max(T,mes[i].t); 118 if(a==0) 119 mes[i].val=1; 120 else 121 mes[i].val=-1; 122 } 123 sort(mes,mes+n,cmp); 124 cal(n); 125 build(1,T,1); 126 int res=-1; 127 for(int i=1;i<=T;i++){ 128 int ans=query(1,T,1,1,i-m-1); 129 update(1,T,1,i,dp[i]+ans); 130 res=max(res,dp[i]+ans); 131 } 132 printf("Case %d: %d\n",cas++,setree[1].num); 133 } 134 return 0; 135 }