Home > OI > DP手记No.1

DP手记No.1


@以下题目大部分是DP,不排除有少数闲杂题目混入
@标了[checked]的题目表示已经实际编程验证,100%放心
@未标[checked]的题目未经验证,仅代表个人参考思路
推荐使用Notepad++进行阅读

Ural

1009 1012 1013:
这三道题叙述相同,规模依次增大,故只考虑1013。
设F(i)为i位的k进制数,且最高位非0;G(i)为i位的k进制数,且最高位为0

F(i)=(F(i-1)+G(i-1))*(k-1)
G(i)=F(i-1)+G(i-1)
答案为F(N),时间复杂度和空间复杂度都为O(N)
或: F(i)=F(i-2)*(k-1)*k

1017
设F(i,j)代表i个brick,每个台阶高度不超过j的方案数
可以推得
F(i,j)=F(i-1,0)+F(i-2,1)+…+F(i-j,j-1)
这个方程的时间复杂度是O(n^3)
写出F(i,j-1)的状态转移方程:
F(i,j-1)=F(i-1,0)+F(i-2,1)+…+F(i-j+1,j-2)
故F(i,j)=F(i,j-1)+F(i-j,j-1) (i>=j)
易知答案为F(N,N-1).

1021[checked]
这题严格来说只能算hash,
开两个hash表分别存储两表数据(原值+32768),
再遍历其中一个hash+判断即可。

1044
设F(i,j)代表前i位的和为j的情况数,则
F(i,j)=sigma(F(i-1,j-k)) k<=j
答案为sigma(F(N/2,i)^2),i为前N/2位数之和的所有可能取值(0~9*N/2)

1056
事实上,我们可以用O(N)的时间求出所有结点与其它结点的最远距离。
显然题目给出了一棵有根树,我们采取树形DP,
计F(i)为i结点到它的子结点的最远距离,则
F(i)=Max{F(j)}+1,其中j是i的子结点
记录G(i)为i结点到其它所有结点的最远距离,
显然对于根结点1这个值就是F(1),
求完某个结点时,保存当前结点的前两大距离值(记可用的一个为MaxG),以及是由哪个结点得到的
然后搜索子结点,用MaxF更新当前值,即
G(i)=Max(F(i),MaxG+1)

1065
以边界上每个哨站为顶点构图
i向j连边,当且仅当在顺时针方向上,从i到j的这一块区域中不包含任何遗迹
可用一个数组F(i,j)记录,用递推的方法:(1-1=n,n+1=1)
F(i,j)=1 F(i,j-1)=1 && 以j-1,j,i构成的三角形中以及i到j-1、i到j的连线上不包含遗迹
F(i,i+1)=1

1078
以每个线段为顶点构图,
若某线段i包含于线段j,
则连一条从i到j的有向边,
求最长路即可(显然图中不可能有环)
或:
将所有线段按左端点坐标排序,左端点相同则按右端点排序(都是从小到大),
再求右端点坐标的最长下降子序列长度即为答案

1102
bool数组F(i)记录可行性
F(i)|=F(i-len[j]) j是一个可行单词且与字符串相应位置匹配

1112
先将所有线段按左端点从小到大排序,左端点相同的按右端点从小到大排序
记F(i)为前i条线段可保留的最大个数,则
F(i)=Max{F(j)}+1,seg[j].x2<=seg[i].x1

1114
记F(i,j,k)为前i个箱子,放j个红球和k个篮球的方案数,则
F(i,j,k)=sigma(F(i-1,j',k')) forall j'<=j && k'<=k

1119
记F(i,j)为从(1,1)到(i,j)的最短路

F(i,j)=Min(F(i-1,j),F(i,j-1))+100
F(i,j)=Min(F(i,j),F(i-1,j-1)+100sqrt(2)) 当前格可以斜穿
内存限制很紧,要使用滚动数组
进一步观察可发现,若可以斜穿,往往是更优的,实际上,我们应当尽量多走斜边,
因此,我们可以将所有可以走斜边的格按坐标排序,然后求最长上升序列,设长度为MaxS,
则答案为(N+M-MAXS*2)*100+MaxS*100sqrt(2)

1138
设F(i)表示从s变到i的最多次数,则
F(i)=Max{F(j)}+1,j为整数,存在整数p使j*(1+0.01p)=i

1142
在一个有序关系中,一串连续的等号可以被视为一个整体,
我们将两个小于号中间的数视作一个部分,并以此划分状态:
设F(i,j)为i个数,有j个部分的不同关系的数目,则
F(i,j)=F(i-1,j)*j+F(i-1,j-1)*(i+1)
比如关系
a<b=c<d=e<f
6个数 4个部分
若在此基础上添加等号,不会增多部分,有4个不同位置
若在此基础上添加小于号,部分数+1,有7个不同位置

1143
这题是求哈密顿回路。一般的哈密顿回路是NP难度的,
但是凸多边形的哈密顿回路有多项式算法,因为路径具有不自交的性质。
设状态
F(i,j,0)表示以i为起点,走遍从i到j的最短路径,
F(i,j,1)表示以j为起点,走遍从i到j的最短路径,
这里的从i到j都是指题目叙述中的逆时针方向。
则可得
F(i,j,0)=min(F(i+1,j,1)+dis(i,j),F(i+1,j,0)+dis(i,i+1))
F(i,j,1)=min(F(i,j-1,0)+dis(i,j),F(i,j-1,1)+dis(j,j-1))
(记1-1=n,n+1=1)
答案要枚举每个点为起点,取最小值

1146
枚举纵方向的区间并将此区间内的数求和,
转化成一维的最大连续子段和问题:
设F(i)表示以第i个数结尾的最大连续子段和
则F(i)=Max(a[i],a[i]+F(i-1))

1148
设F(i,j,k)为最多用i块砖,盖j层塔,塔底恰有k块砖的方案数,可得
F(i,j,k)=F(i-k-1,j-1,k+1)+F(i-k+1,j-1,k-1)
计算一下空间复杂度,需要开约N*H*(M+H-1)大小的数组,即约
32767*60*69=135655380!更何况Ural抠门到只给4M内存,需要大规模优化(以下优化基于C++开不对称数组的方法)
首先考察N<=32767,
假设H和M都是最大值,即60和10,
那么顶层最多有69块砖,总共最多2370块砖,可知N存在大量冗余;
再考察第三维k,我们从最底层H出发可得到:
第H层:M
第H-1层: M-1 M+1
第H-2层: M-2 M M+2
第H-3层:M-3 M-1 M+1 M+3

可见第i层至多有(H-i+1)种情况,总共至多1830种情况
这样要开的数组大小缩小至1830*2370=4337100左右,
同时从M构建出的表格可以知道结果不会大于2^60,用64位整型数据存储即可,
这样总共需要33M左右,仍旧超额
我们可以利用对N的压缩进一步压缩各状态下的最多能用的砖块数,
对于第j层,k块砖,i的最大取值为(k+j-1+k)*k/2,
用程序模拟计算总数组大小,得2474490,内存需要18M
接下来有2种方法:
1 牺牲时间换取空间,先用滚动数组得出总数,
每次从后往前保存尽量多的层数,对所有询问作处理,期望次数不超过5次,可以在1秒内出解。
2 只保存部分解,比如能被5整除的层数的解,其它层数现场搜索

1156
以题目为顶点构图,若两道题目不能出现在同一轮则连边,
可得到若干个连通分量。对每个连通分量中的点作01染色,
统计每个连通分量中染成0或1的个数,再用背包求解即可。

1158
自动机DP…

1163
这题不难在DP,难在计算几何。
DP的状态很好表示,设F(S1,S2)表示我方剩余棋子状态为S1,对手剩余棋子状态为S2,是否有必胜策略。
每个状态可以用一个8位的二进制数表示。
每轮要枚举所有可能转移到的状态,进行转移。这里就出问题了:角度可以是实数,如何枚举?
假设有一条自某圆出发的路径,与若干个圆相交,
我们总可以找到这些圆的一个,使得这条直线调整到与这个圆相切,并仍旧与其它圆相切或者相交。
所以枚举量就减少到枚举当前操作的圆+与其它每个圆的公切线。

1167
设F(i,j)代表前i匹马,分到前j个马厩的最小不快乐度,
定义第i匹马到第j匹马分到同一个马厩中的不快乐度为W[i,j],
再定义A[i]表示从第1匹马到第i匹马中白马数量,B[i]表示从第1匹马到第i匹马中黑马数量,
则W[i,j]=(A[j]-A[i-1])*(B[j]-B[i-1])
状态转移方程为
F(i,j)=Min{F(k,j-1)+W[k+1,i]},时间复杂度为O(N^2*K)
事实上可以证明该方程满足决策单调性,
篇幅所限,这里只给出W凸性的证明,为此只需证
W[i,j]+W[i+1,j+1]<=W[i+1,j]+W[i,j+1] (i<j)
将W定义式代入并展开,则只需证
A[i]*B[i]+A[j-1]*B[j-1]-A[i]*B[j-1]-A[j-1]*B[i]+A[i+1]*B[i+1]+A[j]*B[j]-A[i+1]*B[j]-A[j]*B[i+1]
<=A[i+1]*B[i+1]+A[j-1]*B[j-1]-A[i+1]*B[j-1]-A[j-1]*B[i+1]+A[i]*B[i]+A[j]*B[j]-A[i]*B[j]-A[j]*B[i]
只需证
A[i]*B[j]+A[i+1]*B[j-1]+A[j-1]*B[i+1]+A[j]*B[i]<=A[i]*B[j-1]+A[i+1]*B[j]+A[j-1]*B[i]+A[j]*B[i+1] (1)
显然A,B都是单调递增的,
若i<=j-2,即i<i+1<=j-1<j,则
A[i]<=A[i+1]<=A[j-1]=B[j-1]>=B[i+1]>=B[i]
(1)式左边为逆序和,右式为乱序和,由排序不等式知此式成立
若i=j-1,则(1)式化为
A[i]*B[i+1]+A[i+1]*B[i]+A[i]*B[i+1]+A[i+1]*B[i]<=A[i]*B[i]+A[i+1]*B[i+1]+A[i]*B[i]+A[i+1]*B[i+1]
只需证 A[i]*B[i+1]+A[i+1]*B[i]<=A[i]*B[i]+A[i+1]*B[i+1]
又得A[i]<=A[i+1], B[i]<=B[i+1], 左式为逆序和,右式为顺序和,由排序不等式知此式成立。

1171
二分答案,每个格子的分值减去这个答案,用DP判断是否存在一条路径使得分值和不小于0,
要先预处理每一层从一个格子到另一个格子的最大分值。

1172[checked]
设F(x,y,z,now)表示岛1上剩x个,岛2剩y,岛3剩z个城市,当前在岛now的方案数,这里只写岛1的方程:
F(x,y,z,1)=y*F(x,y-1,z,2)+z*F(x,y,z-1,3)
注意边界情况,最后还要回到岛1,所以结尾只能在岛2或岛3。
这题需要高精度计算。

Poj
1037
设F(i,j,0/1)表示以i开头,长度为j,上升或下降的序列个数,
但由于数字不可重复,这样做会有后效性,因此我们需要转换状态
显然,对于j个互不相同的数,我们并不关心它们的具体大小,而只关心它们之间的大小关系,
这样我们就可以将它们一一映射到1~j,“以i开头”就改为“以这j个数中第i大的开头”,状态转移方程为:
F(i,j,0)=sigma(F(k,j-1,1)) 1<=k<i
F(i,j,1)=sigma(F(k,j-1,0)) i<=k a := b + 0
Add a,b ==> a := a + b
Sub a,b ==> a := a – b
之后DP,F(i,j,k)表示执行了i条程序1的指令和j条程序2的指令后,变量k的并行期望值,这个值应等于
当前状态下不同操作得到的变量k值的和/所有不同操作的数量
显然分母就是C(i+j,i)
对于分子,取决于具体的决策,刚刚执行完的指令可能是程序1,或程序2的
由于每个语句都被统一成赋值运算
x0 := x1 op1 x2,
若赋值变量x0不是k,则
F(i,j,k)=(F(i-1,j,k)*C(i+j-1,i-1)+F(i,j-1,k)*C(i+j-1,j-1))/C(i+j,i)=(F(i-1,j,k)*i+F(i,j-1,k)*j)/(i+j)
若x0=k,则
F(i,j,k)=((F(i-1,j,x1) op1 F(i-1,j,x2))*i+(F(i,j-1,x1) op1 F(i,j-1,x2))*j)/(i+j)

1093
F(i,j)代表考虑前i个单词,第i个单词所在的行恰好用掉j个字符的最小代价,那么
F(i,j)可以转移到:
F(i,j)+(k-1)^2 -> F(i+1,j+len[i+1]+k)
F(i,j)+500 -> F(i+1,n)
F(i,n) -> F(i+1,len[i+1])

1143
F(i,S)代表现在轮到玩家i,剩余数字集合为S,
是否存在必胜策略,枚举选择的数字进行转移即可

1157
设F(i,j)表示前i个花瓶放前j束花的最大观赏值,则
F(i,j)=Max(F(i-1,j),F(i-1,j-1)+Aesthetic[j,i]),即决策为第i个花瓶是否放花

1178[checked]
先预处理骑士或国王从某格到某格的最小步数。
然后枚举汇聚点,枚举骑士是否接国王,若接国王,接的位置只需在国王初始位置周围共9格进行枚举即可。

1179
先枚举删掉的边,这样多边形就变成一条链,然后对链进行DP(以下顶点编号为断链之后重新编号)

F(i,j)代表第i个顶点到第j个顶点操作后可得到的最大分值,
G(i,j)代表第i个顶点到第j个顶点操作后可得到的最小分值,

F(i,j)=Max{F(i,k) op F(k+1,j),G(i,k) op F(k+1,j),F(i,k) op G(k+1,j),G(i,k) op G(k+1,j)}
G(i,j)=Min{F(i,k) op F(k+1,j),G(i,k) op F(k+1,j),F(i,k) op G(k+1,j),G(i,k) op G(k+1,j)}
其中i<=k<j; op
为第k个顶点和第k+1个顶点之间的边的操作符

1180
可参见黑书P152
设F(i)表示前i个任务的代价以及之后任务的等待代价之和的最小值,则
F(i)=Min{F(j)+W[j+1,i]}
其中W[j+1,i]=(S+SumT(j+1,i))*SumF(j+1,n)
进一步可证明该方程满足决策单调性,因此可优化到O(nlogn)
此外本题有O(n)算法,详见黑书

1239
F(i,j)代表前i个数字划分为若干段,且最后一段为j~i,是否能组成严格单调递增序列,则
F(i,j)|=F(j-1,k) 1<=kc或m>n或m与n不同奇偶时概率为0,否则设F(i,j)代表取出i块后桌子上有j块的概率,则
F(i,j)=F(i-1,j-1)*(c-j+1)/c+F(i-1,j+1)*(j+1)/c
这个方程复杂度高达O(nc),对于极限数据很难在时限内出解
更高效的方法是利用生成函数,原问题可转化为:
取出n块巧克力,其中有m种颜色取出奇数块,(c-m)种颜色取出偶数块的概率,
即函数((e^x-e^(-x))^m*(e^x+e^(-x))^(c-m))*C(c,m)/(2^c*c^n)
的展开式中x^n的分子系数,
具体求法从略,详见黑书

1323[checked]
贪心。分别将手中的牌、其他人手中的牌按降序排序,设两个指针分别指向它们。
每一轮:若我方>对方,则胜出一轮,我方后移;否则我方、对方同时后移

1390
黑书P123例题。
首先将颜色序列压缩,相同颜色的连续方块合并,每一段存储为color[i]和len[i],
设F(i,j,k)表示将(color[i],len[i]),(color[i+1],len[i+1]),…,
(color[j-1],len[j-1]),(color[j],len[j]+k)消去的最大分值,考虑最后一段,
要么立刻消去,要么“贴”到前面某一段上一起消去,则
F(i,j,k)=Max{F(i,j-1,0)+(len[j]+k)^2,F(i,p,len[j]+k)+F(p+1,j-1,0)}

1432
设F(i)表示以第i个电码开头的种类数,则
F(i)=sigma{F(j)},需满足第i~第j-1个电码与某个单词匹配,可以用hash来判断

1456
将所有物品按利润降序排序。每次找利润最大的物品,放到deadline之内的最晚的时间。
但是这样做的复杂度是O(n^2),为了减少寻找最晚时间的时间耗费,我们用并查集进行优化,
每一天以它之前最晚的空闲时间作为根结点,若当前天空闲则以自己为根结点。
每次查询后更新并进行路径压缩。

1475
双重广搜。首先BFS搜索当前结点的箱子位置所能扩展到的位置,再根据此位置BFS人所应走的最短路线。注意判重。
此题当然也可以用DP(记忆化搜索)做,设F(x1,y1,x2,y2)表示箱子的坐标为(x1,y1),且人的坐标为(x2,y2)的最小步数,
转移时枚举人是否推箱子,以及具体的移动方位,每次转移复杂度O(1),双重BFS和DP的复杂度都是O(R^2*C^2)

1485
设F(i,j)表示前i座饭店放置j座仓库的最小距离,则
F(i,j)=Min{F(i,k)+Cost[k+1,j]}
其中Cost表示在第k+1至第j座饭店中放置一座仓库的最小距离,
可以证明,达到最小距离时仓库必位于k+1~j的中位数位置,
该数组可以预处理求得。

1505
经典问题。设F(i,j)表示前i个人抄前j本书,最小的每个人时间的最大值。则
F(i,j)=Min{Max(F(i-1,k),Sum[k+1,j])}
但是对于此题,最好的算法并非DP。使“最大值最小”可以让我们联想到二分。
对答案进行二分,用贪心判断是否满足要求,进而逐渐缩小区间,即可得解。

Categories: OI Tags: , , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: