pku1278 BOAT dp+rmq

题目描述的好含糊
是这样的
有n个客户要租船,租期为ti天。每个用户给供应商若干个选择列表:di,pi,即商户在d日期前提供服务的话(这里指提供完服务,即在di-ti天前即将船租给用户)就可以支付p单位的钱。
租赁必须采取先到先服务的策略(可以选择不租给某个用户),即时间的分配是从前到后按顺序的(这个是划分状态的基础)。
好了。说说做法
设状态dp[i][j]为已经考虑完第i个用户且第i个用户在第j时间还船产生的最大效益。
dp方程就很明了了dp[i][j]=max{dp[i-1][j-ti]+val[i]}复杂度为O(n2*计算val的复杂度)
vali理解为在第i个用户的可选列表中di>=j中支付价格的最大值。这里如果朴素的实现的话就是O(n)复杂度,整个算法就是O(n3),对于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 


posted on 2010-11-06 15:51 yzhw 阅读(219) 评论(2)  编辑 收藏 引用 所属分类: DP

评论

# re: pku1278 BOAT dp+rmq 2015-02-06 17:18 无极吧

3
2
2
2
4
1 2 5
2 4 10
3 6 12
2 4 14
你的程序输出31,正确答案27  回复  更多评论   

# re: pku1278 BOAT dp+rmq[未登录] 2015-02-07 08:44 yzhw

不好意思,我已经退役2年多了,可能记不得当时实现时候哪里有问题,你可以自己验证下如果用朴素方法求val,而不用RMQ,你的样例能否得出正确值。如果是,那么可能我当时实现RMQ有BUG  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2015年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜