标签:动态规划

题意有 $N$ 个小球,每个小球的坐标为 $(x_i,y_i)$ ,即水平为 $x_i$ ,高度为 $y_i$ , 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ,每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数,分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球,求最高分数。$N\le 1000$ 。题解比较容易想到区...
题解 动态规划 动态规划-区间DP
省选/NOI-
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ,可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ,用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ,$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...
题解 动态规划 动态规划-区间DP
省选/NOI-
题意给一个长度为 $N$ 的木板染色,木板有初始颜色,要求染成一种颜色。每次可以选择一段连续的格子染色,颜色可以被覆盖。求至少要染多少次。$N\le 50$ 。题解用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。当 $S_l=S_r$ 时,可以在染一边时顺便把另一边染了,即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。否则可以枚举中间点 ...
题解 动态规划 动态规划-区间DP
提高+/省选-
题意有 $N$ 座城堡和 $S$ 个玩家,每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍,玩家之间两两都会有独立的城堡争夺,占领第 $i$ 个城堡的收益是 $i$。现在已知 $S$ 个玩家的驻军情况,求如何分配兵力,可以获得最大收益。$S,N\le 100 \ \ \ \ M\le 20000$ 。题解很显然的背包问题,只是需要预处理一下重量。用 $v[i][j]...
题解 动态规划 动态规划-背包DP
提高+/省选-
题意有一个只有 $-1,0,1$ 的序列,每次操作可以使 s[i]+=s[i-1] ,求最少要操作几次使得序列单调不降。无解输出 BARK序列长度 $N\le 1000000$ 。题解用 $f[i][j]$ 表示前 $i$ 个数,$s[i]=j-1$ 时的最少操作次数。然后对于每一位的值分类讨论即可。代码里很显然了,我懒得再写一遍了。#include<bits/stdc++.h>...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有一个序列,要求修改尽可能少的数,使得这个序列变成单调上升序列。输出最少需要修改多少个数,以及在修改最少的前提下,每个数改变的绝对值之和的最小值。序列长度 $N\le 35000$ 。题解子问题1如果只是单调不降就很简单,但这题要求单调上升。假设可以保留 $S_i,S_j \ (i < j)$ ,则需要满足 $S_j - S_i \geq j-i$ ,即 $S_j - j\geq ...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有 $A,B$ 两个字符串,要从 $A$ 中选出 $k$ 个子串,按原顺序排列后形成 $B$ 。求方案数。$A,B$ 的长度为 $N,M$ ,$N\le 1000 \ , \ M\le 200$ 。题解用 $f[i][j][k]$ 表示取到 $A_i,B_j$ ,选了 $k$ 个子串的方案数。可以枚举当前子串的长度 $l$ ,这样要求 $A_{[i-l+1,i]}$ 和 $B_{[j-l...
题解 动态规划 动态规划-线性DP
提高+/省选-
双倍经验:洛谷1868 饥饿的奶牛题意从 $N$ 个区间中选取一些不重叠的区间,使得总长度最大。$N\le 10000 \ \ L,R\le 30000$ 。题解用 $f[i]$ 表示前 $i$ 个数选取区间的最大总长度,答案即为 $f[n]$ 。如果存在一个区间 $[y,x]$ ,那么 $f[x]$ 就可以从 $f[y]$ 转移过来。方程式为:$$f[x] = \max \begin{ca...
题解 动态规划 动态规划-线性DP
提高+/省选-
题意把 $N$ 个数分成 $M$ 段,要求每段和的方差尽可能小,求最小值。$N\le 3000$ 。题解我这个辣鸡的错误解法方程还是比较容易想到的,用 $f[i][j]$ 表示当前是第 $i$ 段,分到第 $j$ 个数的最优解,方程为:$$f[i][j] = \min_{k=0}^{j-1} (f[i-1][k] + \sum_{p=k+1}^j M\times (X_p - \overli...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意有 $N$ 个工厂,每个工厂与第 $1$ 个工厂的距离为 $X_i$,有成品 $P_i$ 件。需要修建一些仓库,在每个工厂修建的成本为 $C_i$ 。修建完成后要将成品全部运到仓库里,且只能往序号较大的工厂里运输。运输的成本为 $P_i\times (X_j-X_i)$ 。求成本的最小值。$N\le 10^6$ 。题解用 $f[i]$ 表示最后在 $i$ 修仓库的最小成本,枚举上一次修仓...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意农场主养了 $M$ 只猫,它们会到 $N$ 座山上去玩,在 $T_i$ 的时候下山。农场主雇了 $P$ 个员工,员工可以在不同的时刻从第 $1$ 座山出发去接猫。求所有猫等待时间和的最小值。$N,M\le 10^5 \ , \ P\le 100$ 。题解用 $t_i$ 表示接第 $i$ 只猫的最早出发时间,显然 $t_i = T_i - D_{H_i}$ ,然后将所有猫按照 $t_i$ ...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意多重背包问题。题解单调队列优化多重背包。$$f[i][j] = \max_{k=0}^{num[i]} f[i-1][j-k\times c[i]]+k\times w[i]$$令 $a = j \mod c[i] \ , \ b = \lfloor \dfrac{j}{c[i]} \rfloor $ :$$f[i][j] = \max_{k=b-num[i]}^{b} \{f[i-1]...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意有 $N$ 个格子,每个格子有权值。最开始每次只能跳 $d$ 格,可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。$N\le 500000$ 。题解可以对 $g$ 二分答案,然后进行验证。令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值,转移方程式为:$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\...
题解 动态规划 算法-二分/三分 动态规划-线性DP
提高+/省选-
题意从一个数列中选出一些数,要求不能有超过 $k$ 个连续的数,求这些数的最大和。数列长度 $N\le 100000$ 。题解令 $f[i]$ 表示前 $i$ 个数的最优解,$sum[i]$ 表示前缀和,转移方程式为:$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$$$f[i] = \max_{j=i-k}^i \{f[j-1] - sum...
题解 动态规划 动态规划-线性DP 动态规划-单调队列优化DP
提高+/省选-
题意给出一个 $N$ 点 $M$ 边的有向图,令 $1\rightarrow N$ 的最短路长度为 $d$ ,求 $1\rightarrow N$ 的长度不超过 $d+k$ 的路径条数。多组数据。 $N\le 100000$ ,$M\le 200000$ 。题解先跑一次反向最短路,记 $i\rightarrow n$ 的最短路长度为 $dis[i]$ 。用 $d(i,j)$ 表示 $i\ri...
题解 动态规划 动态规划-图上DP
省选/NOI-