2298: [HAOI2011]problem a

分析：

　　每个人说的话，可以转化成区间[l,r]的人的排名是一样的，于是就转化成了区间带权覆盖问题。

　　f[i]表示到第i个人，的最多有多少人说了真话，n-f[n]为答案。

　　对于f[i]，如果没有线段以i为右端点，f[i] = f[i-1]。

　　如果有的话，那么这些线段可以选或不选，不选f[i]=f[i-1]；选，它可以从最近的不想交的地方转移，找到此线段的左端点，然后f[i]=max(f[l]+min(w[l,i],i-l+1))；w表示线段的权值，j-l+1，表示这条线段最大的价值。

　　

　　另一种写法：f[i]表示到第i条线段的最大价值，那么可以二分找到第一个不和这条线段相交的线段，从这里转移。

 

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include