牛客508497775号

题解

/ 注册

全部文章 / 题解（共3篇）

Tallest Cow题解

题目大意就是有n个奶牛排成一排，他们的身高都是正整数，从1到n编号，最高的奶牛是第I个，高度为H。给出r个信息，每个信息为“a号牛能看到b号牛”，即a+1号到b-1号牛都比a号牛和b号牛低，要求求出每个奶牛可能的最高身高。朴素的算法可以模拟每一个信息，让a+1号到b-1号牛的身高都减一，时间复杂度...

2020-11-04

0 667

Strange Towers of Hanoi题解

题意就是要求解出有n个盘子四个塔的汉诺塔问题。三个塔的经典汉诺塔很好解。用sum[n]表示有n个盘子三个塔的答案，能得到如下递推式d[n]=d[n-1]*2+1表示先把n-1个盘子从1塔移到2塔，再把第n个盘子移到3塔，再把n-1个盘子从2塔移到3塔。现在考虑4塔的情况。用num[n]表示n个盘子四...

2020-10-31

0 733

最短Hamilton路径

题目让求最小值，这种只求最小（大）值而不要方案的一般都跟动态规划有关。所以这题也可考虑用DP解。题目要求有n-1个点时的最短Hamilton路径，而如果我们能先求出有n-2号点时的最短路径，就只需找出这n-2个点中那个点到n-1号点最近就行了。这就是本题的一个子问题，显然有n-1个点时的最优解可以...

2020-10-22

0 617