[BZOJ2298] [HAOI2011]problem a

本文主要是介绍[BZOJ2298] [HAOI2011]problem a，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=2298

题目大意

$n个人说自己前面有a_i个人，后面有b_i个人$，可能排名相同
询问最少有几个人说谎

题解

通过每个人说的话，我们可以得到这个人所在的区间，即这段人的排名相同
那么如果两个区间有交集且不吻合，那么一定有一个人说谎
吻合的话，吻合段数大于区间长度也有人说谎
这样，我们将问题转化为一些有权的线段，询问最大权(没说谎的人数)
$dp[i]:表示[1,i]的这个区间内最大的权值和$
$dp[i]=dp[i-1]$
$如果i是某条线段的右端点$
$dp[r]=max\{dp[i],dp[l-1]+v[这条线段]\}$

uses math;
constmaxn=100000;
varx:array[0..maxn,1..3]of longint;w:array[0..2*maxn,1..3]of longint;dp,s:array[0..maxn]of longint;i,j,k:longint;n,m,a,b,tt,len,cnt:longint;
procedure sort(l,r:longint);
var a,b,c,i,j:longint;
begini:=l; j:=r; a:=x[(l+r)div 2,2]; b:=x[(l+r)div 2,1];repeatwhile (x[i,2]<a)or((x[i,2]=a)and(x[i,1]<b)) do inc(i);while (x[j,2]>a)or((x[j,2]=a)and(x[j,1]>b)) do dec(j);        if not(i>j) thenbeginc:=x[i,1]; x[i,1]:=x[j,1]; x[j,1]:=c;c:=x[i,2]; x[i,2]:=x[j,2]; x[j,2]:=c;inc(i); dec(j);end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;procedure init(a,b,c:longint);
beginw[len,1]:=b; w[len,2]:=c;if w[a,3]=0 then w[a,3]:=len else w[w[a,1],3]:=len;w[a,1]:=len; inc(len); 
end;beginreadln(n); cnt:=n; m:=0;for i:=1 to n dobeginreadln(b,a);inc(a); b:=n-b;if a>b then continue;inc(m); x[m,1]:=a; x[m,2]:=b;end;n:=m; sort(1,n); {x[i,2],x[i,1]}x[n+1,1]:=cnt+1; x[n+1,2]:=cnt+1;tt:=0; m:=0;for i:=1 to n+1 doif (x[i,1]<>x[i-1,1])or(x[i,2]<>x[i-1,2])then begin x[m,1]:=x[i-1,1]; x[m,2]:=x[i-1,2]; x[m,3]:=min(tt,x[m,2]-x[m,1]+1); tt:=1; inc(m); endelse inc(tt);dec(m); len:=cnt+1;for i:=1 to m doinit(x[i,2],x[i,1],x[i,3]);for i:=1 to cnt dobegintt:=w[i,3]; dp[i]:=dp[i-1];while tt<>0 dobegindp[i]:=max(dp[i],dp[w[tt,1]-1]+w[tt,2]);tt:=w[tt,3];end;end;writeln(cnt-dp[cnt]);
end.

这篇关于[BZOJ2298] [HAOI2011]problem a的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---