首页 > 代码库 > codeforces 278Div1 B题
codeforces 278Div1 B题
虚拟参赛的时候没想到是线段树，看到很多人都过了，也蛮着急的。
首先用二分+线段树的方法更新DP[i]：它表示以A[i]为结尾可以最前到哪个位置；
再用线段树计算ans[i]：它表示当前i个A元素可以最少分成多少个pieces，ans[i]=1+min(ans[j])，dp[i]-1<=j<=i-L。
over.
16 #define N 100000+5 17 18 int a[N],dp[N],Ans[N]; 19 struct segment { 20 int l,r; 21 int Min,Max,ans; 22 } seg[4*N]; 23 24 struct diff { 25 int Max,Min; 26 diff(int x=0,int n=0):Max(x),Min(n) {} 27 }; 28 29 void build(int p,int l,int r) 30 { 31 seg[p].l=l, seg[p].r=r, seg[p].ans=-1;; 32 if (l==r) { 33 seg[p].Min = seg[p].Max = a[l]; 34 return; 35 } 36 build(p<<1,l,(l+r)>>1); 37 build((p<<1)+1,((l+r)>>1)+1,r); 38 39 seg[p].Min = min(seg[p<<1].Min, seg[(p<<1)+1].Min), 40 seg[p].Max = max(seg[p<<1].Max, seg[(p<<1)+1].Max); 41 } 42 43 diff query1(int p,int l,int r) 44 { 45 if (l<=seg[p].l && seg[p].r<=r) { 46 return diff(seg[p].Max,seg[p].Min); 47 } 48 49 diff t1,t2; 50 bool f1=false, f2=false; 51 if (seg[p<<1].r>=l) 52 f1=true, t1=query1(p<<1,l,r); 53 if (seg[(p<<1)+1].l<=r) 54 f2=true, t2=query1((p<<1)+1,l,r); 55 56 if (f1) { 57 if (f2) 58 return diff(max(t1.Max,t2.Max), min(t1.Min,t2.Min)); 59 else 60 return t1; 61 } 62 else 63 if (f2) 64 return t2; 65 return diff(0,0); 66 } 67 68 int query2(int p,int l,int r) 69 { 70 if (l<=seg[p].l && seg[p].r<=r) { 71 return seg[p].ans; 72 } 73 74 int t1=-1,t2=-1; 75 if (seg[p<<1].r>=l) 76 t1=query2(p<<1,l,r); 77 if (seg[(p<<1)+1].l<=r) 78 t2=query2((p<<1)+1,l,r); 79 80 if (t1==-1) { 81 return t2; 82 } 83 else { 84 if (t2==-1) 85 return t1; 86 else return min(t1,t2); 87 } 88 89 } 90 91 void add(int p,int i,int newans) 92 { 93 if (seg[p].l==seg[p].r) { 94 seg[p].ans=newans; 95 return; 96 } 97 98 if (i<=seg[p<<1].r) 99 add(p<<1,i,newans);100 else101 add((p<<1)+1,i,newans);102 103 if (seg[p<<1].ans==-1) {104 seg[p].ans = seg[(p<<1)+1].ans;105 }106 else {107 if (seg[(p<<1)+1].ans==-1)108 seg[p].ans=seg[p<<1].ans;109 else110 seg[p].ans=min(seg[p<<1].ans,seg[(p<<1)+1].ans);111 }112 }113 114 int main()115 {116 //freopen("b.txt","r",stdin);117 118 int n,s,l;119 cin>>n>>s>>l;120 for (int i=1;i<=n;i++) scanf("%d",&a[i]);121 build(1,1,n);122 for (int i=1;i<=n;i++) {123 int L=1,R=i-1;124 dp[i]=i;125 while (L<=R) {126 int mid = (L+R)>>1;127 diff tmp = query1(1,mid,i);128 if (tmp.Max-tmp.Min<=s) {129 R=mid-1;130 dp[i]=mid;131 }132 else {133 L=mid+1;134 }135 }136 }137 138 139 for (int i=1;i<=n;i++) {140 if (i<l) {141 Ans[i]=-1;142 continue;143 }144 int tmp=-1;145 if (i-l>0 && dp[i]-1<=i-l)146 tmp=query2(1,max(1,dp[i]-1),i-l);147 if (dp[i]==1) tmp=0;148 149 if (tmp==-1)150 Ans[i]=-1;151 else152 Ans[i]=tmp+1, add(1,i,Ans[i]);153 }154 cout<<Ans[n]<<endl;155 156 return 0;157 }
codeforces 278Div1 B题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。