题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

f[i]表示背包已用i容量时能得到的最大价值，value[i]表示第i个物体的价值，size[i]表示第i个物品所要占据的背包容量（或者说是重量、时间之类的）。那么我们的决策就是要不要把当前处理的物品放入背包中。我们可以得到方程$f[i]=\max(f[i],f[i-size[i]]+value[i])$。题目链接采药

Dijkstra算法是一种用于求最短路径的算法，用于求一个节点到其他所有节点的最短路径。与其他的最短路径算法一样，都采用松弛操作，并且运用了贪心的思想。适用于处理不存在负边权的稀疏图，算法的时间复杂度为 $O(N^2)$ ,采用堆优化后可以达到 $O(N\log N)$ 。

SPFA算法是Bellman-Ford（蛤？你说你不知道Bellman-Ford算法？）算法的队列实现方法，采取动态逼近的方式来求得单源最短路，时间复杂度为O（ek）e为边数，k是所有点进队的平均次数。适用于不存在负权回路的稀疏图。

By吴雨航