题意

有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。
Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。

题意：

桥长度为$L$ ，分布有$n$ 个石子，青蛙每次可以跳 $[S,T]$ 的距离,问青蛙过桥至少要踩多少个石子。

$(1<=S,T<=10,m<=100,a_i<=10^9, a_i 表示第i个石子的位置)$

solution

题意

给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。

solution

不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意边界情况。

题意

现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种

对于一个格子，里面会有以下几种字符：

0：这个格子没有烈焰，且其左右两个格子均没有烈焰

题意

给一个小图和一个大图，问大图有多少个子图形状和小图一样。

solution

最多只有8个点，因为每个点标号可能不一样，因此可以全排列枚举所有点的位置，然后判断小图有的边大图是否也有（因为原来边的属性还在），并通过hash进行去重。

题意

给定长度为 $n$ 的数组，$q$ 次询问 $[1,l]+[r,n]$ 组成的新数组中不相同的元素个数。$(1<=n,q<=1e5)$

solution1

一眼莫队题，主要是要想怎么样把它变成一个连续的区间。其实只要把整个数组再复制一遍接上就可以了，则原来查询的 $r$ 变为 $l$，$l$ 变为 $l+n$，区间连续。

题意

给定两个字符串，各取出一个子串接在一起，求最长回文子串的长度。

solution

先考虑普通的求最长回文子串的dp做法:

题意：让你安排课程，保证每学期的课不能冲突，问最少需要几个学期。

solution：

因为 n 只有15，可以考虑状压dp。用二进制每位的1/0表示当前是否学习该课程，可以得到 n 个二进制位，那么所有的可能性有 1<<n 种，预处理 g[s] 表示 s 所代表课程的是否可以在一个学期内学完（对于当前要学的所有课程的学时进行标记，若有重复标记则不可能在一学期学完），f[s] 维护学完当前课程所花费的最少学期，枚举子集进行转移。
答案的状态应该是所有课全部修完，即 $f[(1<<n)-1]$。时间复杂度 $O(2^n m n)$。

题意

n 条木板，每条木板都被分成 m 段且每一段都有要涂的颜色，有 t 次机会涂色，每次可以选择一条木板的连续一段涂成同一种颜色，问最多可以涂对多少段。

solution

考虑四维dp的做法。$dp[i][j][k][0/1]$ 代表到第 $i$ 条第 $j$ 段时涂 $k$ 次，当前段涂红或蓝$(0/1)$的最大正确数，可以得到转移方程：

题意

给定一个 $n$ 个点 $m$ 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。

solution

求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，将走过的边加入边集，建一个新图出来。为了使路径最短，考虑最小生成树，但需要满足题目的条件，因此我们对新的图进行排序，以高度为第一关键字从大到小排，再以路径长度为第二关键字从小到大排，这样可以保证点最多的同时路径最短。