2020 年 11 月刷题日志

P3842 守望者的逃离

2020-11-10 | 题目链接 | </> 代码

在 $n\times n$ 的格上，在每行中各有一条线段 $(i,l_i)\to (i,r_i)$。

你从 $(1,1)$ 出发，只能沿着格子直走，最终走到 $(n,n)$。要求沿途经过所有的线段，且所走路程长度尽量的短。

显然是一行一行的递推。维护两个数据，一个是走完该行后停留在左侧的，记作 ${\mathrm{D}\mathrm{P}}_l$，相应的停留在右侧的记作 ${\mathrm{D}\mathrm{P}}_r$。

若停在左侧，可能从上一行的右侧走来，也可能是由左侧走来，故转移方程有

$${\mathrm{D}\mathrm{P}}_l[i]=r_i-l_i+min\{{\mathrm{D}\mathrm{P}}_l[i-1]+|l_{i-1}-r_i|,{\mathrm{D}\mathrm{P}}_r[i-1]+|r_{i-1}-r_i|\}$$

右侧类似

P1541 乌龟棋

2020-11-10 | 题目链接 | </> 代码

初始有四种卡片，消耗后分别可以前进 $1$、$2$、$3$ 和 $4$ 格。棋盘上每个点都有个分数，求从第 $1$ 格到达第 $N$ 格途径分数的最大值。

设状态 $F[i,j,k,w]$ 为使用 $i$ 张前进 $1$、……、$w$ 张前进 $4$ 之后的状态，容易得到转移方程

$$F[i,j,k,w]=max\left\{\begin{array}{c}dp[i-1,j,k,w]\\ dp[i,j-1,k,w]\\ dp[i,j,k-1,w]\\ dp[i,j,k,w-1]\end{array}\right\}+a[i+2j+3k+4w]$$

处理一下边界情况，滚动数组即可。

P1833 樱花

2020-11-11 | 题目链接 | </> 代码

略

P1064 金明的预算方案

2020-11-11 | 题目链接 | </> 代码

略

P1941 飞扬的小鸟

2020-11-12 | 题目链接 | </> 代码

略

P1160 队列安排

2020-11-16 | 题目链接 | </> 代码

略

P1106 删数问题

2020-11-17 | 题目链接 | </> 代码

略

P2058 海港

2020-11-17 | 题目链接 | </> 代码

略

P3367 并查集

2020-11-26 | 题目链接 | </> 代码

略

P1226 快速幂

2020-11-26 | 题目链接 | </> 代码

略

P3383 线性筛素数

2020-11-26 | 题目链接 | </> 代码

略

P1636 Einstein 学画画

2020-11-27 | 题目链接 | </> 代码

略

P1880 石子合并

2020-11-30 | 题目链接 | </> 代码

环形队列上有 $n$ 堆石子，可以把相邻的两堆合成一堆，每次合并的得分是新一堆的石子数。

求最终分数的最小值和最大值。

考虑 $dp(i,j)$ 是将区间 $[i,j]$ 的石子全部合并的最大值。于是状态转移方程为

$$dp(i,j)=\underset{i⩽k⩽j}{max}(dp(i,k)+dp(k+1,j)+s(i,j))$$

其中 $s(i,j)$ 是 $[i,j]$ 中所有石子数。

然而不能通过先 $i$ 再 $j$ 再 $k$ 的循环来递推，运算顺序值得注意。

细节：前缀和、循环开两倍。