刷题记 III-I

WIND LINER —— DAISHI DANCE - beatlessBEST...Mellow Relaxation

前言

狂补DP QAQ

Optimal Binary Search Tree - UVA - 10304

题意

最优二分搜索树问题

思路

定义DP状态， 表示区间[i,j]构成的子树的权值和最小值，那么 ，即现在选择k为根，那么当前的权值和就是左右子树的权值和，但是由于左右子树深度全部下降了1，因此要加上sum，补上这部分的权值

Recovering BST - CodeForces - 1025D

题意

给定一个升序序列，问题能否构造出一棵二分搜索树，使其每条边上的两点都满足不互质

思路

如果和上题一样，定义 为能否构成这样一棵子树，那么显然 可以从 和 转移而来，但是我们此时需要多加一个信息即谁为根，也就是定义为 为以k为根，区间[l,r]构造的树能否成立，但是完成这个算法就需要O(n^4)的时间，显然是不可取的

因此需要换一种定义状态的方式，定义 为区间[i,j]组成的树可以为根j+1的左子树， 为区间[i,j]组成的树为根i-1的右子树，那么

画图可知以上二式

最后的答案就再枚举一遍k，能使得 为1，则为Yes，否则为No

Lighting System Design - UVA - 11400

题意

给定n种灯泡，每种灯泡由电压值V，电源费用K，单个费用C和数量L，不同种类的灯泡必须用不同的电源，同一种则可以用相同的电源，现在可以将一些灯泡换成电压更高的另一些灯泡，问最小费用

思路

首先可以肯定的是，对于一种灯泡，要么全换，要么不换，毕竟只换一半还要多一个电源的钱，不划算的

然后按照电压值从小到大排序，那么第二件可以肯定的是，对于某一个灯泡，换成它的灯泡必定是以他为终点的一段连续子区间

举个栗子，假如由1 2两种灯泡，1没有换成2，这时候加入一个电压更高的灯泡3，那么假如1换成3更划算，又因为1没有换成2，说明1换成2是不划算的，那么2换成3当然会更划算，所以1和2就得全部换成3，如果1换成3不划算，那么2可能换成3，也可能不换成3，但都是一个连续子区间

定义DP状态 代表排序后到第i个灯泡时所花的费用最小值，那么 ，其中sum是数量的前缀和

Multiplication Puzzle - POJ - 1651

题意

最优矩阵链乘问题

思路

定义DP状态 代表区间[i,j]链乘的最小值，那么

Brackets sequence - UVA - 1626

题意

括号序列匹配问题，要求添加最少括号使得给定的字符串括号匹配，并且要求输出该字符串

思路

定义DP状态 代表区间[i,j]括号匹配的最大值，那么

最难的地方应该是如何输出，按照紫书的写法，只需要最后根据 的计算结果递归输出即可

Partitioning by Palindromes - UVA - 11584

题意

给定字符串，要求划分出最少的回文子串区间

思路

首先定义一个DP状态 用来记录子串[i,j]是否为回文串，则

再定义一个DP状态 代表到第i个字符时所能划分出的最少回文子串区间数，则

Color Length - UVA - 1625

题意

有两个序列，每次可以将其中一个序列的头部字符取走放入一个新序列中，定义价值为新序列中每个字符最开始出现的位置和最后出现的位置的距离之差的和，求价值最小值

思路

首先预处理出每个字母在序列中第一次和最后一次出现的位置，然后定义DP状态 代表在第一个字符串到i，第二个字符串到j时，出现但未结束的字母个数，再处理完 （如何处理见代码，试出来的 T^T）

然后定义DP状态 为第一个字符串到i，第二个字符串到j时的价值最小值，则

因为根据DP方程来DP的话，初态处理比较麻烦，所以下面代码做了个变形