题意在 $N\times M$ 的棋盘上放若干个炮，要求不能互相攻击，求方案个数。其中 $N,M\le 100$ 。题解将题意转化一下就是每行每列都不能放超过 $2$ 个棋子，那么可以用 $f[i][j][k]$ 表示前 $i$ 行，有 $j$ 列是有 $1$ 个棋子，有 $k$ 列是有 $2$ 个棋子的合法方案数。那么没有棋子的列数即为 $M-j-k$ 。然后分类讨论。不放继承上一步的状态...
题意定义半连通图为对于 $\forall (u,v)$ ，存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的有向路径。给出一个有向图，求最大半连通子图中的节点个数以及最大半连通子图的个数。其中点数 $N\le 100000$ ，边数 $M\le 1000000$ 。题解显然连通图也属于半连通图，那么可以先缩点，记录每个点的新编号 $scc[]$ 以及包含节点个数 $siz[]$ ，并删...
首先预处理一下两个单词 $s[i],s[j]$ 是否安全并记录在 $can[i][j]$ 中，用 $f[i]$ 代表包含第 $i$ 个单词的安全组有多少个。枚举每一个小于当前单词的单词，如果他们俩安全，那么当前单词和 枚举单词所在的安全组成员 在一起也一定是安全的，所以加上答案即可。$$f[j]= \begin{cases} f[j] \\ f[j]+f[i] , can[i][j] \&a...
显然用dp，用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间，枚举上一个分组的最后一辆车 $j$ 进行转移，方程式为：$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$其中 $tmax$ 是这一组中最...
就是一道区间dp+高精，最开始还想拿int_128来水水的，结果算算还是不太够，就老老实实写了高精。$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值，转移方程式为：$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$每次转移时枚举放乘号的位置 $(mid)$...
晚上做了洛谷TG试炼场的DP lv1 模块，还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行，我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了，按理来说应该要写高精的，但是我发现这玩意写高精如果没有运算符重载版的是真的恶心，然后__int128水过去了。#includ...
很久没写过总结了。紫书做了那么多道题，但是我的动规并没有找到什么感觉，也就只有普及难度的可以不看题解写，剩下的都是看着题解写完的，我还是太弱了。这里还是来总结一下吧。例题9-1 UVa1025-A Spy in the Metro$f[i][j]$表示在车站i，时刻是j，还剩多少时间（根紫书略有不同）决策有三个，上左边的车，上右边的车，如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...