📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3192| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

求大神指点 G家面经题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
公司有很多office,你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。

这道题应该怎么解? 跪求大神指点啊

评分

参与人数 1大米 +1 收起 理由
parkhunter + 1 谢谢你的介绍!

查看全部评分


上一篇:问一道L 家的高频面经题吧
下一篇:第二遍刷题,求小伙伴儿一起~

本帖被以下淘专辑推荐:

推荐
杰西Jesse 2015-12-2 12:33:32 | 只看该作者
全局:
写了一下,感觉复杂度有点高啊。。。求大神们指导。。。
  1. public class MaxHoliday{
  2.         public int findMax(int [][] holiday, int [][]flight,int hour){
  3.                 int [][] dp = new int [flight.length][holiday.length];
  4.                 for(int i = 0; i < holiday.length; i++)
  5.                         dp[i][0] = holiday[i][0];
  6.                 for(int i = 1; i < holiday[0].length; i++){
  7.                         // i stand for week
  8.                         for(int j = 0 ; j < flight.length; j++){
  9.                                 // j is origin office
  10.                                 for(int k = 0; k < flight.length; k++){
  11.                                         // k is destination office
  12.                                         if(flight[j][k]<=hour){//flight time needs to be smaller than some time.
  13.                                                 //new office holiday equals the original holiday + new office holiday
  14.                                                 dp[k][i] = Math.max(dp[k][i],dp[j][i-1] + holiday[k][i]);
  15.                                         }
  16.                                 }
  17.                         }
  18.                 }
  19.                 for(int i = 0; i < dp.length; i++){
  20.                         for(int j = 0; j< dp[0].length; j++){
  21.                                 System.out.print(dp[i][j] + "\t");
  22.                         }
  23.                         System.out.println();
  24.                 }
  25.                 int maxHour = 0;
  26.                 for(int i = 0; i < flight.length; i++){
  27.                         maxHour = Math.max(maxHour, dp[i][holiday.length-1]);
  28.                 }
  29.                 return maxHour;
  30.                
  31.         }
  32.         public static void main(String args[]){
  33.                 int [][] holiday = {//column is week,holiday[i][j] stands for in week i, office j's holiday
  34.                         {0,1,2,1,0},
  35.                         {0,0,0,0,1},
  36.                         {1,1,0,1,2},
  37.                         {2,1,1,2,1},
  38.                         {1,2,3,1,2}};
  39.                 int [][] flight ={//flight[i][j] stands for fly time from city i to city j
  40.                         {0,6,3,5,2},
  41.                         {6,0,1,3,4},
  42.                         {3,1,0,2,1},
  43.                         {5,3,2,0,2},
  44.                         {2,4,1,2,0}};
  45.                 MaxHoliday mh = new MaxHoliday();
  46.                 System.out.println(mh.findMax(holiday,flight,3));
  47.         }
  48. }
复制代码
回复

使用道具 举报

推荐
staycrazy 2016-2-5 13:10:30 | 只看该作者
全局:
plich 发表于 2015-11-18 23:16
应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

我觉得题意不明。

因为有路径长度限制,可能要走回头路才能达到最大值。比如说:

A---B----C
      |
      D---E----F----.....-----Z

连通情况如上。第二周周末在C,第三周周末却回到了B,第四周才去D。这里B的假期可以重复计算吗?

如果B的假期可以重复计算,那么到达一个假期非常多的办公室之后就可以赖着不走了

如果B的假期不可以重复计算,那么第三周的假期就不能+V(3, B)
回复

使用道具 举报

推荐
plich 2015-11-18 23:16:22 | 只看该作者
全局:
tq5124 发表于 2015-11-18 12:02
感觉dp就可以?OPT(i,j)表示在第i个星期呆在j办公室的情况下,从年初到现在获得的假期。然后每次计算OPT(i, ...

应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

最顺溜的follow up就是问最大假期的方案,那么更新OPT(i,j)的时候顺手记下来trace就行了
回复

使用道具 举报

🔗
vivianbuan 2015-11-18 11:52:30 | 只看该作者
全局:
感觉是个max flow.太久没做图论了。。。手动马克等大神解答
回复

使用道具 举报

🔗
tq5124 2015-11-18 12:02:30 | 只看该作者
全局:
感觉dp就可以?OPT(i,j)表示在第i个星期呆在j办公室的情况下,从年初到现在获得的假期。然后每次计算OPT(i,j) = max(OPT(i-1, k)),k是所有能在一个周末飞到j办公室的办公室。二维数组保存dp结果,算一遍后求个最大的假期
回复

使用道具 举报

🔗
tq5124 2015-11-19 01:38:14 | 只看该作者
全局:
plich 发表于 2015-11-18 23:16
应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

啊把vacation忘掉了。。。thx~
回复

使用道具 举报

🔗
 楼主| queeniejing 2015-11-19 03:38:09 | 只看该作者
全局:
明白了 谢谢楼上各位大神
回复

使用道具 举报

🔗
hj867955629 2015-11-19 12:05:08 | 只看该作者
全局:
这题我觉得应该用状态机,就是每次产生节点给能到达的office,然后再产生下一个level的节点,直到最后,取那个level假期最大值。
回复

使用道具 举报

🔗
queqichao 2015-12-2 13:14:04 | 只看该作者
全局:
假设有N个office,M个week,V(i,j) 是第i个礼拜 office j的假期数。另外建一个有向图图,每个node代表一个office,i->j 表示可以从j到i。
最后做DP,建一个M X N 的table T,T(i,j) 纪录的在第i个礼拜停在office j时,已经休的假的最大值。T(i+1, j) = max(T(i,k), 能从k到j) + V(i + 1, j)
回复

使用道具 举报

🔗
杰西Jesse 2015-12-3 00:05:31 | 只看该作者
全局:

cycle的意思是指? 从A->B->A
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表