題意是這樣：有N個牛，可以為FJ工作一段時間[si,ti]，F(xiàn)J要支付給他pi工資。FJ需要整天都有牛為他工作，問他至少需要支付多少錢。
首先，可以對區(qū)間按照右端點為第一關(guān)鍵字排序，狀態(tài)dp[pos]表示聘用第pos個牛時并且之前的區(qū)間都已經(jīng)覆蓋需要支付的錢，一個樸素的DP轉(zhuǎn)移可以表示為
dp[pos]=min{dp[i]} ei>=si。當(dāng)然，我們立刻會發(fā)現(xiàn)一點，如果決策dp[j]>dp[i]，而j<i，即ej<ei，那么j這個決策是多余的。因此，我們可以維護一個單調(diào)隊列，通過二分查找來找到滿足ei>=si的dp[i]最小值，整個算法復(fù)雜度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