题意：司令部的将军们打算在 $N \times M$ 的网格地图上部署他们的炮兵部队。一个 $N \times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署...

题意从数列$a$中选出若干数，但不能有超过$k$个连续的数字被选择，求选出数字的最大和数据范围：$1 \le n \le 10^5,1 \le a_i \le 10^9$题解用$f[i]$表示选到第$i$个时的最大值，显然，在$j \in [i-k,i]$一定存在至少$1$个断点，否则存在超过$k$的连续段，所以枚举该断点$$f[i]=max(f[j-1]+a[j+1]+ \dots +a[...

题意求$c=\frac{a}{b} \bmod 19260817$的值数据范围：$0 \le a,b \le 10^{10001}$题解$$ \begin{aligned} \frac{a}{b} &= a \cdot b^{-1} \\ & \equiv (a \bmod p) \cdot (b^{-1} \bmod p) \end{aligned} $$转化为$a \ti...

题意：求基环树最大带权独立集。数据范围： $N \le 1000000$题解：算法：树形dp分析题意：由“每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己）”建立有向图，将每个人 $x$ 最厌恶的人 $y$ 记为其父节点 $fa[x]=y$ ，可得每个节点有且仅有一条出边，且无自环。由于共有 $N$ 条边，所以该图为基环树。考虑到基环树的性质，删边后必定构成一棵树。分别以删去的边连接的...

题意对于一个$01$序列，有$5$种操作：$0 \ a \ b$ 把$[a,b]$区间内的所有数全变成$0$$1 \ a \ b$ 把$[a,b]$区间内的所有数全变成$1$$2 \ a \ b$ 把$[a,b]$区间内的所有数全部取反$3 \ a \ b$ 询问$[a,b]$区间内总共有多少个$1$$4 \ a \ b$ 询问$[a,b]$区间内最多有多少个连续的$1$对于每个询问，输出答...

题意略数据范围：$0 \le w,t \le 2000,1 \le p \le 2000,1 \le bp_i \le ap_i \le 1000,1 \le as_i,bs_i \le p$题解算法：动态规划用$f[i][j]$表示第$i$天持有$j$股股票，前$i$天的最大收益首先，若从第$i$天开始买股票，有$$f[i][j]=-ap_i \cdot j$$其中$j \in [0,as...

题解求$1 \sim n$的全排列中逆序对数为$k$的数量数据范围：$n,k \le 1000$题解用$f[i][j]$表示$1 \sim i$的全排列中逆序对数为$j$的数量考虑将$i$插入$1 \sim i-1$的数列中。因为$i$比该数列中所有数都大，所以$i$放在哪里都能产生贡献，贡献的范围为$i-1$（放在首位）$\sim$ $0$（放在末位），可得状态转移方程$$f[i][j]=...