[关闭]
@zzzc18 2017-10-25T23:22:51.000000Z 字数 2193 阅读 440

NOIP2013 花匠

线段树


我可以说不会正解么?

也相当于DP,对于当前的数值,我们求以这个数为波峰/波谷结尾的最长的波峰、波谷交替的序列,这样就可以用线段树维护值域,每个值对应的是以这个值结尾的最长的满足条件的数列长度

在这里

  1. for(i=2;i<=N;i++){
  2. int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;
  3. int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;
  4. F.modify(1,num[i],val_g+1,val_f+1);
  5. }

就是以当前数为波峰的数列长度
就是以当前数为波谷的数列长度
将这个数值插入线段树时,将上面求的两个值+1再交换(波峰波谷交替)就行了

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 100000+9;
  6. int b[MAXN];
  7. int num[MAXN];
  8. int n,N;
  9. class Segment_Tree{
  10. private:
  11. struct T{
  12. int ls,rs,left_range,right_range;
  13. int val_f;
  14. int val_g;
  15. }tree[MAXN*4];
  16. int lazy_min[MAXN*4];
  17. int lazy_max[MAXN*4];
  18. int cnt;
  19. void update(int x){
  20. tree[x].val_f=max(tree[tree[x].ls].val_f,tree[tree[x].rs].val_f);
  21. tree[x].val_g=max(tree[tree[x].ls].val_g,tree[tree[x].rs].val_g);
  22. }
  23. public:
  24. int Build(int l,int r){
  25. int now=++cnt;
  26. tree[now].left_range=l;
  27. tree[now].right_range=r;
  28. if(l==r){
  29. return now;
  30. }
  31. int mid=l+r>>1;
  32. tree[now].ls=Build(l,mid);
  33. tree[now].rs=Build(mid+1,r);
  34. update(now);
  35. return now;
  36. }
  37. int getmax_f(int k,int l,int r){
  38. if(l<=tree[k].left_range && tree[k].right_range<=r){
  39. return tree[k].val_f;
  40. }
  41. int mid=tree[k].left_range+tree[k].right_range>>1;
  42. int re=-1;
  43. if(l<=mid)re=max(re,getmax_f(tree[k].ls,l,r));
  44. if(r>=mid+1) re=max(re,getmax_f(tree[k].rs,l,r));
  45. return re;
  46. }
  47. int getmax_g(int k,int l,int r){
  48. if(l<=tree[k].left_range && tree[k].right_range<=r){
  49. return tree[k].val_g;
  50. }
  51. int mid=tree[k].left_range+tree[k].right_range>>1;
  52. int re=-1;
  53. if(l<=mid)re=max(re,getmax_g(tree[k].ls,l,r));
  54. if(r>=mid+1) re=max(re,getmax_g(tree[k].rs,l,r));
  55. return re;
  56. }
  57. void modify(int k,int pos,int val1,int val2){
  58. if(tree[k].left_range==tree[k].right_range){
  59. tree[k].val_f=val1;
  60. tree[k].val_g=val2;
  61. return;
  62. }
  63. int mid=tree[k].left_range+tree[k].right_range>>1;
  64. if(pos<=mid)modify(tree[k].ls,pos,val1,val2);
  65. else modify(tree[k].rs,pos,val1,val2);
  66. update(k);
  67. }
  68. }F;
  69. int main(){
  70. scanf("%d",&N);
  71. int i;
  72. for(i=1;i<=N;i++){
  73. scanf("%d",&num[i]);
  74. b[i]=num[i];
  75. }
  76. sort(b+1,b+N+1);
  77. n=unique(b+1,b+N+1)-(b+1);
  78. for(i=1;i<=N;i++)
  79. num[i]=lower_bound(b+1,b+n+1,num[i])-b;
  80. F.Build(1,n);
  81. F.modify(1,num[1],1,1);
  82. int ans;
  83. for(i=2;i<=N;i++){
  84. int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;
  85. int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;
  86. F.modify(1,num[i],val_g+1,val_f+1);
  87. }
  88. printf("%d\n",max(F.getmax_f(1,1,n),F.getmax_g(1,1,n)));
  89. return 0;
  90. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注