第二周的动规章节，H题数独貌似是用DLX求解精确覆盖问题，暂时搁置到复习。

A 劲歌金曲

n首歌，所剩时间t， 每首歌不超过3分钟，歌曲总长度总比t大，只有劲歌金曲长达663s。

唱尽可能多的歌，并且尽可能晚离开。

题解

注意dp[i]容纳的是背包容量为i（时间限制为i）时最多可以唱多少歌及相应时间，该时间并不一定是i，比较时先比较歌数，再比较时间。递归表达式为：

dp[i]=max⁡(dp[i−songs[k]]+t[k],dp[i])dp[i]=\max (dp[i-songs[k]]+t[k],dp[i])

dp可以用省内存方式：只记录一行，循环时从右往左（如果递推式只用到左上边）

时间限制应该是t-1，因为假如前面的歌用到了最后1s，不如替换成删除后换成劲歌金曲。所以无论如何最后都要留出1s给劲歌金曲。

B 最小回文子串分割

一个字符串。

分割字符串为数个子串后每个子串均为回文串的最少子串数。

题解

这题debug可真费劲。。。

首先可以先复用最长回文串的代码，也就是dp[i][j]表示i到j是否是回文串。（这里用动规或者直接暴力循环时间复杂度没有区别，空间暴力循环甚至还小点）

下面是重点：对于字符串类容易想到用前i个字符串表示子问题（group[i]表示前i字母的字符串回文串分组最少的个数）。因此我们这里递推为：

group[j]={min⁡(group[j],group[i]+1)if dp[i+1][j]=1group[j]if dp[i+1][j]≠1group[j]=\left\{\begin{array}{lrl}\min (group[j],group[i]+1) & if\ dp[i+1][j]=1\\group[j]& if\ dp[i+1][j]\ne 1\\\end{array}\right.

初始化条件：dp[i]\[i]=1，group[i]=i。

可以使用string数据类型读字符串，用起来比较方便。

重新赋值不需要用clear()清除自动覆盖。

注意ij从0开始，为了考虑到i+1可能为0的情况，i从-1开始取值，单独讨论出来前j个（dp[0][j]）正好为回文串的情况（数组越界）

C 单向旅行商

给一张不超过100×100的整数表格，其中每个数代表到达格子的开销。

要求输出从左到右走格子（只能向右上、右侧、右下一格走，第一行和最后一行互通）最小开销和字典序第一的路径。

题解

递推式异常简单，但是由于考虑输出字典序第一的答案，顺推需要把所有可能答案排一下序（但是一直WA），找了两个小时错误硬是没找到，但是HDU的就过了，无语。改成逆推后又对了（因为在递推的时候默认使用字典序靠前的状态，不需要考虑比较字典序）。所有错还是在顺推找最小字典序的过程中，然而试验了简单的样例依然没发现问题。

这里我用的是sort对各答案排序，sort是可以用在嵌套的vector上的，结果就是对各vec按字典序排序。

所以以后需要回溯还是逆推吧。

D 赤壁之战

N个情报的价值，按固定顺序排列为序列s，需要选择M个递增的情报泄密且使其和最小。

泄密的情报价值和。

题解

本题很容易想到递归表达式：

dp[i][j]=∑k<j,s[k]<s[j]dp[i−1][k]dp[i][j]=\sum_{k<j,s[k]<s[j]} dp[i-1][k]

dp[i][j]为以j结尾的长度为i的递增子序列个数.

但这样暴力去求会是一个O(mn2)O(mn^2)复杂度直接裂开。

这里看到解法非常机智，将所有数递增排列然后用二叉平衡树组织，因为每次二叉平衡树求和操作正好就是序列前面比自己小的那些数求和。

如何保证只有自己前面的那些比自己小的数被算进去了呢？刚开始二叉平衡树为空，只有我们遍历到某一个数之后我们才将此处的dp[i-1][j]add到树上的第j个情报排序后的位置，这样每次遍历查询到的就是i-1的dp值的和，这样就满足了要求。

这样同时利用了BIT的两个操作，太机智了。

当然，还需要注意我们得知道每一个数在递增排序后的位置，这需要我们提前记录。

参考: 【学习笔记】动态规划—各种 DP 优化 - AcWing

嘿，突然发现code还有bug：没考虑数字相同的情况。需要结构体排序的时候让同数字指向同一个位置——尽管评测机并没有测出来这一点。
不过c++有一种lower_bound方法可以用指针找到数组第一个比指定数大的数的位置，虽然lower_bound复杂度为O(logN)O(logN)，但用了却TLE？？？原因暂且未知。

E 间谍乘车

车站之间的间隔，始发地和目的地的发车时间。已知可以瞬间从车站下车并上车。

准时到达目的地的最少的等待时间，如不能到达则输出impossible。

题解

刚开始一直以为在要求时间内到达就行，寻思那我岂不是一直坐到目的地就行，果然不对，必须在正好的时间到。首先我们计算两个表left和right，分别记录每个车站每个时刻是否有向左开或者向右开的车。dp[i][j]表示车站i上j时刻到目的地的最少等待时间，显然边界条件dp[n][j]=0，我们逆推i，从n-1计算dp。如果i站j时刻有向右的列车dp[i][j]=dp[i+1][j+distance[i]]，向左同理；如果没有dp[i][j]=dp[i][j+1]+1。递推表达式为：

dp[i][j]={min⁡(dp[i+1][j+distance[i]],dp[i][j+1]+1)if left[i][j]=1 and right[i][j]≠1min⁡(dp[i−1][j+distance[i−1]],dp[i][j+1]+1)if right[i][j]=1 and left[i][j]≠1min⁡(dp[i+1][j+distance[i]],dp[i−1][j+distance[i−1]],dp[i][j+1]+1)if left[i][j]=1 and right[i][j]=1dp[i][j+1]+1if left[i][j]≠1 and right[i][j]≠1dp[i][j]=\left\{\begin{array}{lrl}\min (dp[i+1][j+distance[i]],dp[i][j+1]+1) & if\ left[i][j]=1\ and\ right[i][j]\ne 1\\\min (dp[i-1][j+distance[i-1]],dp[i][j+1]+1) & if\ right[i][j]=1\ and\ left[i][j]\ne 1\\\min (dp[i+1][j+distance[i]],dp[i-1][j+distance[i-1]],dp[i][j+1]+1) & if\ left[i][j]=1\ and\ right[i][j]=1\\dp[i][j+1]+1 & if\ left[i][j]\ne 1\ and\ right[i][j]\ne 1\\\end{array}\right.

要在几个取值里取最小。

F 巴比伦塔

给一些三条边长给定的长方体，每一种提供无穷个。

它们按照长宽分别严格递减堆起来最高高度。

题解

debug再次在非算法部分花了大部分时间：数组越界。好吧原谅我脑子抽了忘了边界应该是case数*3，甚至还换了3种数据结构存长宽高。本题可以利用长宽大小排序，从小往大进行dp计算。因为最小的答案是确定的，所以可以求出dp初始值。

G 计数问题

给两个数l、r。

两个数之间所有数0-9出现的次数。

题解

用找规律嗯做出来了。实际上这道是经典数位DP题：dp[i]表示0-i位填满（999…999）包括前导0的0-9的计数，0-9应该出现相同次且dp[i]=dp[i-1]*10+10^(i-1)，前一部分是前i-1位的贡献，后一部分是最后一位的贡献。对于这道题我们可以求0到任意数的计数和，然后用0到r的减去0到l-1的。如何求0到任意数的计数和？从高到低遍历每一位的贡献：每次先计算该位对所有数字的贡献，再加上后面数对首位比该数小的所有数的贡献，再减去前导0的贡献，最后补上后i-1个数对该位对应数字的贡献。

H 数独

todo

I 修复长城

长城有一些损伤部分需要机器人修复，每一部分的修复都需要开销，推迟修复开销会增大，要求给出最小开销修复的算法。机器人的初始位置和移动速度，长城损伤的位置和每个位置立即开始修复的开销和单位时间增长的开销。机器人初始位置一定不在损伤位置。

修好长城的最小开销。

题解

由于机器人修好i、j两个点后必然顺带修好了[i,j]所有的点，所以我们可以应用区间DP（问题可以由两个区间的子问题合并+合并的开销）：dp[i][j]为修好i到j所用的最小开销，由于机器人修好i到j的部分后必然从i出来或从j出来我们分别设这两种情况为dp[i][j][0]和dp[i][j][1]。dp[i][j][0]=max{dp[i-1][j][0]+额外开销,dp[i][j-1][1]+额外开销}，dp[i][j][1]同理。递推表达式为：

dp[i][j][0]=max⁡(dp[i−1][j][0]+cost,dp[i][j−1][1]+cost′)dp[i][j][1]=max⁡(dp[i−1][j][0]+cost,dp[i][j−1][1]+cost′)dp[i][j][0]=\max(dp[i-1][j][0]+cost,dp[i][j-1][1]+cost')\\dp[i][j][1]=\max(dp[i-1][j][0]+cost,dp[i][j-1][1]+cost')

J 服务器设置

通过数组给出一棵树（边为N-1条）的连接状态。一个图需要满足：每个cilent有且只有一个server。每个server可以服务所有相邻的cilent。

最少的server数量。

题解

树形DP，即利用树结构DFS递归的子结构同时做DP。假设我们求出了所有子树的情况，求当前根节点的递归表达式。

在本题中，我们对子树根节点分三种情况：

  • 它是服务器，那么子节点任取。dp[i][0]=在其所有子节点中选dp[u][0],dp[u][1]最小求和
  • 它是客户，父节点是服务器，那么子节点必不为服务器。dp[i][1]=其所有子节点中选dp[u][2]求和
  • 它是客户，父节点也是客户，那么子节点必包含一个且只有一个服务器。遍历所有子节点dp[i][2]=其所有子节点中选dp[u][0]和dp[u'][2]求和的最小值→dp[u'][2]可以简化为dp[i][1]-dp[u][2]

设i的子节点集S，递推表达式为：

dp[i][0]=∑u∈Smin⁡(dp[u][0],dp[u][1])dp[i][1]=∑u∈Sdp[u][2]dp[i][2]=min⁡u∈S(∑u′∈S−{u}dp[u′][2]+dp[u][0])=dp[i][1]+min⁡u∈S(dp[u][0]−dp[u][2])dp[i][0]=\sum_{u\in S}\min(dp[u][0],dp[u][1])\\dp[i][1]=\sum_{u\in S}dp[u][2]\\dp[i][2]=\min_{u\in S}(\sum_{u'\in S-\{u\}}dp[u'][2]+dp[u][0])\\=dp[i][1]+\min_{u\in S}(dp[u][0]-dp[u][2])

前两种情况在子节点遍历循环内部，但第三种可以放在循环外，因为循环中可以求前两个（累加），求第三个则需要遍历每种子节点情况，可以先在dfs后存储子节点，然后在循环外求第三种情况。据此我门需要将第三种边界设置为无限大（由于第一次dfs到根节点的取min操作）。

我们通过以下方式构建树：

struct Node{
	int to,nex;
} edge[N<<1];
int head[N];
int cnt;
void add(int p,int q){
	edge[cnt].to=q;
	edge[cnt].nex=head[p];
	head[p]=cnt++;
}

参考：Perfect Service

其中to为该节点相邻的边的节点编号

nex为该点相邻的上一个点在edge的编号（按记录顺序）

head[p]节点p相邻的节点中的最后一个在edge的编号（按记录顺序）