题意是这样：有N个牛，可以为FJ工作一段时间[si,ti]，FJ要支付给他pi工资。FJ需要整天都有牛为他工作，问他至少需要支付多少钱。
首先，可以对区间按照右端点为第一关键字排序，状态dp[pos]表示聘用第pos个牛时并且之前的区间都已经覆盖需要支付的钱，一个朴素的DP转移可以表示为
dp[pos]=min{dp[i]} ei>=si。当然，我们立刻会发现一点，如果决策dp[j]>dp[i]，而j<i，即ej<ei，那么j这个决策是多余的。因此，我们可以维护一个单调队列，通过二分查找来找到满足ei>=si的dp[i]最小值，整个算法复杂度nlogn。
具体分析见周大牛论文/Files/yzhw/range.rar
1
import java.io.*;
2import java.util.*;
3class node implements Comparable<node>
4
{
5
int s,e,val;
6 public int compareTo(node pos)
7
{
8 return e-pos.e;
9
}
10
}
11public class Main {
12
13 /** *//**
14 * @param args
15 */
16 static node arr[];
17 static int dp[];
18 static int stack[][],top=-1;
19 static int search(int pos)
20 {
21 int s=0,e=top,mid=0;
22 while(s<=e)
23 {
24 mid=(s+e)/2;
25 if(stack[mid][1]>=pos)
26 e=mid-1;
27 else
28 s=mid+1;
29 }
30 return s;
31 }
32 public static void main(String[] args) throws IOException{
33 Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
34 int n=in.nextInt(),m=in.nextInt(),e=in.nextInt();
35 arr=new node[n];
36 dp=new int[n];
37 stack=new int[n][2];
38 for(int i=0;i<arr.length;i++)
39 {
40 arr[i]=new node();
41 arr[i].s=in.nextInt();
42 arr[i].e=in.nextInt();
43 if(arr[i].e<arr[i].s)
44 {
45 int t=arr[i].e;
46 arr[i].e=arr[i].s;
47 arr[i].s=t;
48 }
49 arr[i].val=in.nextInt();
50 }
51 Arrays.sort(arr);
52 int i,ans=Integer.MAX_VALUE;
53 for(i=0;arr[i].s>m&&i<n;i++);
54 if(i>=n||arr[n-1].e<e) System.out.println(-1);
55 else
56 {
57 dp[i]=arr[i].val;
58 if(arr[i].e>=e) ans=Math.min(ans, dp[i]);
59 stack[++top][0]=dp[i];
60 stack[top][1]=arr[i].e;
61 for(++i;i<n;i++)
62 {
63 int pos=search(arr[i].s-1);
64 if(pos>top)
65 if(arr[i].s<=m)
66 dp[i]=arr[i].val;
67 else
68 continue;
69 else
70 {
71 dp[i]=stack[pos][0]+arr[i].val;
72 if(arr[i].s<=m)
73 dp[i]=Math.min(dp[i], arr[i].val);
74 }
75 while(top>=0&&stack[top][0]>=dp[i]) top--;
76 stack[++top][0]=dp[i];
77 stack[top][1]=arr[i].e;
78 if(arr[i].e>=e) ans=Math.min(ans, dp[i]);
79 }
80 if(ans==Integer.MAX_VALUE)
81 System.out.println(-1);
82 else
83 System.out.println(ans);
84 }
85
86
87 }
88
89}
90
91