题目描述的好含糊
是这样的
有n个客户要租船，租期为t
i天。每个用户给供应商若干个选择列表：d
i,p
i,即商户在d日期前提供服务的话（这里指提供完服务，即在d
i-t
i天前即将船租给用户）就可以支付p单位的钱。
租赁必须采取先到先服务的策略（可以选择不租给某个用户），即时间的分配是从前到后按顺序的（这个是划分状态的基础）。
好了。说说做法
设状态dp[i][j]为已经考虑完第i个用户且第i个用户在第j时间还船产生的最大效益。
dp方程就很明了了dp[i][j]=max{dp[i-1][j-t
i]+
val[i]}复杂度为O(n
2*计算val的复杂度)
vali理解为在第i个用户的可选列表中d
i>=j中支付价格的最大值。这里如果朴素的实现的话就是O(n)复杂度，整个算法就是O(n
3)，对于n=100这种数据应该没问题了。不过可以用rmq优化到O(logn)。具体实现方法见程序
1 import java.util.*;
2 class rmq
3 {
4 int data[];
5 int arr[][];
6 public rmq(ArrayList<choose> data)
7 {
8 this.data=new int[data.size()];
9 for(int i=0;i<data.size();i++)
10 this.data[i]=data.get(i).mount;
11 arr=new int[data.size()][20];
12 init();
13 }
14 private void init()
15 {
16 for(int i=0;i<data.length;i++)
17 arr[i][0]=data[i];
18 for(int len=1;len<=data.length;len<<=1)
19 for(int i=0;i+(1<<len)<=data.length;i++)
20 arr[i][len]=Math.max(arr[i][len-1], arr[i+(1<<(len-1))][len-1]);
21 }
22 public int query(int s)
23 {
24 int e=data.length-1;
25 int len=(int)(Math.log(e-s+1)/Math.log(2)+1e-6);
26 return Math.max(arr[s][len],arr[e-(1<<len)+1][len]);
27 }
28
29 }
30 class choose implements Comparable<choose>
31 {
32 int dead,mount;
33 public choose(int d,int m)
34 {
35 dead=d;
36 mount=m;
37 }
38 public int compareTo(choose pos)
39 {
40 return dead-pos.dead;
41 }
42
43 }
44 public class Main {
45
46 /**
47 * @param args
48 */
49 static int find(ArrayList<choose> data,int pos)
50 {
51 int s=0,e=data.size()-1;
52 while(s<=e)
53 {
54 int mid=(s+e)>>1;
55 if(data.get(mid).dead>=pos)
56 e=mid-1;
57 else
58 s=mid+1;
59 }
60 return e+1;
61 }
62 public static void main(String[] args) {
63 Scanner in=new Scanner(System.in);
64 while(in.hasNext())
65 {
66 int num=in.nextInt();
67 ArrayList<choose> list[]=new ArrayList[num+1];
68 for(int i=0;i<list.length;i++)
69 list[i]=new ArrayList<choose>();
70 int time[]=new int[num+1];
71 for(int i=1;i<=num;i++)
72 time[i]=in.nextInt();
73 num=in.nextInt();
74 while((num--)!=0)
75 {
76 int id=in.nextInt();
77 list[id].add(new choose(in.nextInt(),in.nextInt()));
78 }
79 for(int i=1;i<time.length;i++)
80 Collections.sort(list[i]);
81 int dp[]=new int[250];
82 Arrays.fill(dp,-1);
83 dp[0]=0;
84 int res=0;
85 for(int i=1;i<time.length;i++)
86 {
87 rmq q=new rmq(list[i]);
88 for(int j=list[i].get(list[i].size()-1).dead;j-time[i]>=0;j--)
89 {
90 if(dp[j-time[i]]!=-1&&(dp[j]==-1||dp[j]<dp[j-time[i]]+q.query(find(list[i],j))))
91 dp[j]=dp[j-time[i]]+q.query(find(list[i],j));
92 }
93 }
94 for(int i=0;i<dp.length;i++)
95 res=Math.max(dp[i],res);
96 System.out.println(res);
97 System.out.println();
98 }
99
100 }
101
102 }
103