分类: [动态规划]

NOIP2009道路游戏

题目描述 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段 马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为 1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在 一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个 机器人工厂和第 i+1 个机器人工厂(1 ≤ i ≤ n-1),第 n 段马路连接第 n 个机器人工厂和第 1 个机器人工厂。 游戏过程中,每个单位时间内,每段马路上 ......

浅谈平行四边形优化(包含正确性证明)

1.概述 平行四边形优化是一个神奇的东西,可以将时间复杂度为$\Theta(n^3)$的常规区间动态规划问题优化成$O(n^2)$。我们先抛出一个常规的区间DP转移方程: $$m(i,j) =\begin{cases} \displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \ 0 &\text{if } i=j \ \infty &\text{if } i>j \end{cases}$$ 如果要可以进行平行四边形优化,该式还要满足:对于所有的$i\le i'<j \le j’$,有: $w(i’,j’)\le w(i,j’)$ (1.1) $w(i,j)+w(i’,j ......

BZOJ5248[2018多省省队联测]一双木棋

题目传送门 方法一 看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。 code: #include&lt;bits/stdc++.h&g ......

BZOJ1096 [ZJOI2007]仓库建设

题目传送门 这是一道比较裸的动态规划斜率优化 考虑f[i]表示前i个工厂,其中第i个一定建了仓库的最小费用。 s1[i]表示i号点到n号点的距离 s2[i]表示1~i号点的所有物资运到n号点的费用,s2[i]=s2[i-1]+s1[i]*p[i] s3[i]表示1~i号点的物资数量 $$f[j]=min_{j=0}^{i-1}{f[j]+s2[i]-s2[j]-s1[i]*(s3[i]-s3[j])}$$ 考虑对于i的两个决策点j,k(j<k),所以(s3[k]-s3[j])>0假设k比j优,即 $$f[j]+s2[i]-s2[j]-s1[i](s3[i]-s3[j])>=f[k]+s2[i]-s2[k]-s1[i](s3[i]-s3[k])$$ $$f[j]-s2[j]-f[k]+s2[k]>=s1[i]*(s3[k]-s3 ......

BZOJ2286 消耗战

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 C++ #include <cstdio> #include <algorithm> #include <cstring> const long long INF = 1e18; int edgenum; int vet[600000], val[600000], nextx[600000], head[300000]; int fa[300000][22]; long long f[300000]; int cnt; int ......

BZOJ4521手机号码

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include&lt;cstdio&gt;; #include&lt;algorithm&gt;; #include&lt;cstring&gt;; using namespace std; long long l,r; long long num[20][10][10][2][2][2]; int a[20]; long long dfs(int len,int p1,int ......