題目描述的好含糊
是這樣的
有n個(gè)客戶要租船，租期為t
i天。每個(gè)用戶給供應(yīng)商若干個(gè)選擇列表：d
i,p
i,即商戶在d日期前提供服務(wù)的話（這里指提供完服務(wù)，即在d
i-t
i天前即將船租給用戶）就可以支付p單位的錢。
租賃必須采取先到先服務(wù)的策略（可以選擇不租給某個(gè)用戶），即時(shí)間的分配是從前到后按順序的（這個(gè)是劃分狀態(tài)的基礎(chǔ)）。
好了。說(shuō)說(shuō)做法
設(shè)狀態(tài)dp[i][j]為已經(jīng)考慮完第i個(gè)用戶且第i個(gè)用戶在第j時(shí)間還船產(chǎn)生的最大效益。
dp方程就很明了了dp[i][j]=max{dp[i-1][j-t
i]+
val[i]}復(fù)雜度為O(n
2*計(jì)算val的復(fù)雜度)
vali理解為在第i個(gè)用戶的可選列表中d
i>=j中支付價(jià)格的最大值。這里如果樸素的實(shí)現(xiàn)的話就是O(n)復(fù)雜度，整個(gè)算法就是O(n
3)，對(duì)于n=100這種數(shù)據(jù)應(yīng)該沒(méi)問(wèn)題了。不過(guò)可以用rmq優(yōu)化到O(logn)。具體實(shí)現(xiàn)方法見(jiàn)程序
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