2017年8月

简要题面

设一个序列的分值为每个数出现次数的平方乘这个数,给定一个长度为n序列,有m组询问$[l,r]$,求从第l个数到第r个数这个子序列的分值。

- 阅读剩余部分 -

$A^\star$算法的经典应用----k短路问题。

$A^\star$算法:设$f(x)=g(x)+h(x)$,其中$g(x)$表示已花费代价,$h(x)$表示预估还需代价($h(x)$要$\le h^\star(x)$)表示每次找到f值最小的拿出来扩展。

给定一个n点m边的有向图,求从s到t的k短路。

首先求出所有点x到t的最短路$dis[x]$,接下来用$dis[x]$作为$h(x)$跑 $A^\star$ ,因为 $h(x)\le h^\star(x)$ ,所以第k次找到t就是k短路。

- 阅读剩余部分 -

题目传送门

题解

状压DP。
将每一只猪打下来/没打下来用一个二进制位表示。
猪的数量不是很多,每一条抛物线至少要打到一只猪,所以可以枚举出所有可行的抛物线,这条抛物线对每一只猪能/不能打下来用一个二进制为表示。

- 阅读剩余部分 -