三分即可。calc(x, y)函数求在点 $(x, y)$ 建造灯塔的最低高度。

时间复杂度 $O(n ^ 2 \times \texttt{某个大常数})$ 。

倍增,处理出每个点往后 $2^i$ 的点、和、最大值,然后倍增乱搞即可。复杂度 $O(n log k)$ ,可过。

需要注意的是 $k$ 是 $10^{10}$ ,需要开 long long。

UVA1220 - Party at Hali-Bula

用 $f[i][0]$ 表示 $i$ 不选所能取到的最大值, $f[i][1]$ 表示选 $i$ 能取到的最大值。

假设当前节点为 $u$ ,孩子节点为 $v$ ,则:

  • $f[u][0] = \sum\limits_{v \in son[u]} \max(f[v][0], f[v][1])$
  • $f[u][1] = \sum\limits_{v \in son[u]} f[v][0]$

关于判断是否有多种情况:我们无需存种数,只要存是否即可,用数组 $d$ 表示,则:

  • 如果当前节点 $u$ 更新状态选中的来自 $v$ 的某个状态存在多种,那么 $u$ 的这个状态也存在多种。
  • 如果 $u$ 节点的某个孩子 $v$ 满足 $f[v][0] == f[v][1]$ ,那么 $f[u][0]$ 存在多种。

去他妈的NOI难度

从 $S$ 到 byx 的每个人连条容量为生命的边,从手气君的每个人到 $E$ 连条容量为生命的边;如果 byx 的这个人能打赢对方的某个人连一条容量为 $1$ 的边,$+1s$ 的话直接加到生命里,最后跑一遍最大流即可。

洛谷3411 - 序列变换

题意

给定一个长度为N的数列Ai。
你可以对数列进行若干次操作,每次操作可以从数列中任选一个数,把它移动到数列的开头或者结尾。
求最少经过多少次操作,可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。

分析

你可以把题意转化为:找到一个不降子序列,使得未选中的数必须不处于子序列的最小值和最大值之间(理由:小于等于最小值的可以移到前面去,大于等于最大值的可以移到后面去)
即找到一个值的区间[L, R],在其中选择一个不降子序列,使得其包含了区间(L, R)中的所有值。
[L, R]表示闭区间,(L, R)表示开区间!)

那么你只要维护一个答案队列,使得其满足题意。每次考虑扩展右区间,同时检查可行性,更新最优解。
需要注意的是,新增的节点值相同时可能会互相产生干扰,我们应当考虑倒序检查,之后顺序入队。

洛谷2962 - 灯

一道非常神奇的题目。

尽管洛谷题解给的都是高斯消元,但实际上这题“普通”的DFS就可以AC。

因为直接DFS一遍的复杂度高达 $O(2 ^ n)$ ,所以我们从两边开始搜索,并把状态存在map里,复杂度降低为 $O(n \times 2 ^ {\frac{n}{2}})$ ,可以水过此题。

LJOJ1244 - 埃及分数

您可以去 Vijos 上搜索此题,不过温馨提示, Vijos 的数据是错的,详情可以参考那题的讨论。

这是一道IDA*经典题,集成了启发式搜索迭代加深的特点进行剪枝。

  • 迭代加深
    本题中,我们限定DFS搜索的层数,如果超过这个层数,就进行剪枝。

  • 启发式搜索
    我们设立一个估价函数,考虑最优情况下的步数。
    本题中我们按照分母从小到大的顺序来DFS埃及分母,所以之后遇到的值就必定大于当前取到的值。
    我们可以通过这个特性来写估价函数,即(a / b) / (1 / u)(其中a / b表示当前的值,u表示剩下能够取到的最小分母)
    做其他题目时一定要注意估价函数所估计的值之多劣于实际情况,而不能比实际情况更优

洛谷2996 - 拜访奶牛

首先,这题无法用贪心实现,下面是一个反例:

贪心反例

贪心的话最大值是 $5$,然而可以在中途放弃一个点从而取到最大值 $6$ 。

我们使用 $f[i][0]$ 来表示到第 $i$ 个点但不取这个点所能获得的最大值,用 $f[i][1]$ 表示到第 $i$ 个点且取这个点所能获得的最大值。

先将每个点都DFS遍历一遍,在回溯时进行DP( $u$ 是当前节点,$G[u][i]$ 是孩子节点):

  • 如果当前节点不选,那么孩子节点选或不选均可
    $f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]) $

  • 如果当前节点选中,那么孩子节点只能不选
    $f[u][1] += f[G[u][i]][0] $

可以看做一张有n个节点的图,每个节点有且仅有一条向外连接的边(可以连自己)。那么图中只可能是环与链的组合。而且链的终点是环,进入环后就不会从环中出去,故一个链只可能接一个环,一个环只可能被一或多的链接。

故我们可以把整个分隔为一个个的环,并把接到他们的链找出来。

  • 环内节点的答案 = 环的长度;
  • 环外节点的答案 = 环的长度 + 当前节点到环的距离。

几趟 $O(n)$ 的搜索就可以搞定问题!

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×