Technology

Google Kick Start 2019 F轮题解

本次的A题比较难,应该算leetcode中的Hard+,类似leetcode 265,但会更难一点:leetcode 265用二维dp即可,而A题需要三维dp

查阅更多的题解,请点击
github传送门

A. Flattening

题目地址

Solution

这道题比较难,做的时候感觉DP不易解,用了贪心,3个小时有一个半小时都在调这个,最后还是没调出来….

后面看了官方题解,果然还是用dp求解

解法

定义wall_i代表第i面墙的高度;定义所有的墙有t种高度,用num[i], i\in [0, t)来表示

看到题,比较容易想到尝试动态规划,二维的状态容易被想到:定义dp[i][j]代表前i个元素,至多包含j对不相同的相同的相邻数字时需要的最少改变次数。此时注意二维很难做状态转移:对于前i-1个元素,再加入一个元素时,由wall_{i-1}wall_{i}的取值,可以有多个状态转移的过程,很难分析,所以需要三维状态

dp[i][j][m]代表前i个元素,至多包含j对不相同的相邻数字, 且其第i个元素为num[m]时需要的最少改变次数,此时所求解为:
min(dp[n][j][m]), for\ j\in[0, k]\ and\ m\in[0, t)

状态转移方程为:

div”>
上述过程中:

  • wall_{i}= num[m]时,有两种情况:wall_{i-1}=wall_i=num[m],不会增加不一致的对数,所以为dp[i-1][j][m]; wall_{i-1}\neq wall_i, 不一致的对数会加一(即前i-1个元素中,最多j-1个不一致),所以是dp[i-1][j-1][n(n\neq m)]
  • wall_{i}\neq num[m]时, 代表第i个数一定会改变一次,所以需要在之前的状态加一

定义minD[i][j]=min(dp[i][j][l]), 其中l\in [0, t), 上述状态转移方程可以简化为:
dp[i][j][m]=min(dp[i-1][j][m], minD[i-1][j-1])+(wall_i!=num[m])

初始状态:

minD[1][0]=0

复杂度分析

分析见上述状态转移方程,O(N^2K) time

代码

code

B. Teach Me

題目地址

Solution

解法

题目求的是(i, j)的个数,其中员工i能教j。令m(i)代表员工i能指导的员工数,则所求结果为\sum_i^n{m(i})。注意求m(i)比较麻烦,令m'(i)代表i不能指导的员工数,则m(i)=n-m'(i)。这里引入m'(i)是因为m'(i)m(i)更易求:当且仅员工j的技能包含员工i的所有技能时,员工i不能指导j,。(思想就类似概率论中,事件A发生的概率不易求,尝试求1-P(A))

可以利用二进制来枚举一个员工技能的子集,最多2^5个,统计所有员工技能的子集出现情况。之后就可以直接求出m'(i)

note:集合可以hash为一个数,然后利用hash table来存储。

复杂度分析

O(2^5*n) time.

代码

code

C. Spectating Villages

题目地址

Solution

解法

Test 1的暴力枚举在这里

题目中的村庄构成了一个树,将任意一个村庄作为根节点,即可将该树转化为一个有根树,对村庄从0到V-1编号,不妨设村庄0为根。

每个村庄都有三个状态:建灯塔且亮、不建灯塔且亮、不建灯塔且不亮。可以用树形dp来枚举这三个状态,令child(i)代表i的子节点集合,values(i)代表i的权值:

  • dp[i][0]=\sum_{j\in child(i)}max(dp[j][0], dp[j][1]):
    村庄i不建灯塔且不亮,此时所有的子节点不能建灯塔

  • 村庄i不建灯塔且亮,此时子节点至少有一个建灯塔(此时取子树权值之和最大的情况,即选择子树亮灯和不亮之间最大,注意至少有一个子树需要亮灯
  • dp[i][2]=values[i]+\sum_{j\in child(i)}max(dp[j][1], dp[j][2])
    村庄i建灯塔且亮,此时子节点可以不建灯塔,或是建任意多的灯塔,但是所有的子节点均被点亮根节点会影响子节点的状态:若子节点未建灯塔且不亮,其状态会变为亮,即dp[j][0]变为dp[j][0]+values[j]

由于知道根节点,可以从上到下递归,所求结果为max(dp[0][0], dp[0][1], dp[0][2]),dp的初始状态为叶子节点的状态:

  • dp[leaf][0]=0
  • dp[leaf][1]=MIN: 对于叶子节点,该状态并没有什么实际上的意义
  • dp[leaf][2]=values_{leaf}

复杂度分析

解法中,利用图的DFS来模拟有根树的遍历过程,所以时间复杂度为:O(n) time.

代码

code

发表评论

电子邮件地址不会被公开。 必填项已用*标注