首先我们很容易看出是一个 DP
然后容易看出是数据结构优化 DP
但是这个限制条件有点鬼畜:
- abs(p[i]-p[j])/2<=(t[i]-t[j])
- p[i]>p[j] ->t[i]*2-p[i]>=t[j]*2-p[j]
- p[i]<p[j] ->t[i]*2+p[i]>=t[j]*2+p[j]
这样的话我只会树套树 (后来想想带修主席树应该也行?)..... 信仰不够去 % 题解
结果发现这两个东西是可以放在一起的, 也就是说如果满足 p[i]>p[j] 和 t[i]*2-p[i]>=t[j]*2-p[j] 那 t[i]*2+p[i]>=t[j]*2+p[j] 也满足 (好像很显然啊是我柿子画得太丑看不出来吗)
就成了水水的二维偏序了...
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- int s[110000];
- int lowbit(int x){return x&-x;}
- void change(int x,int k)
- {
- while(x<=100010)
- {
- s[x]=max(s[x],k);
- x+=lowbit(x);
- }
- }
- int getmax(int x)
- {
- int ret=0;
- while(x>0)
- {
- ret=max(ret,s[x]);
- x-=lowbit(x);
- }
- return ret;
- }
- struct node{int w1,w2,v;}a[110000];
- bool cmp(node n1,node n2){return n1.w1==n2.w1?n1.w2<n2.w2:n1.w1<n2.w1;}
- int lslen,ls[110000];
- int main()
- {
- int W,n,t,p;
- scanf("%d%d",&W,&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d%d%d",&t,&p,&a[i].v);
- a[i].w1=t*2-p;
- a[i].w2=t*2+p;
- ls[++lslen]=a[i].w2;
- }
- sort(a+1,a+n+1,cmp);
- sort(ls+1,ls+lslen+1);
- lslen=unique(ls+1,ls+lslen+1)-ls-1;
- for(int i=1;i<=n;i++)
- a[i].w2=lower_bound(ls+1,ls+lslen+1,a[i].w2)-ls;
- for(int i=1;i<=n;i++)change(a[i].w2,getmax(a[i].w2)+a[i].v);
- printf("%d\n",getmax(lslen));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2787119.html