[TOC]
题目链接
T42357 顺序对齐（Align）
数据范围较小，可以考虑复杂度较大的算法
$ dp[i][j] $ 表示处理到两字符串 $a_i, b_j$ 位置
匹配第 $i, j$ 位时，存在两种情况
- $a[i] == b[j]$ 此时为最佳情况，由贪心得状态转移方程
$dp[i][j] = dp[i-1][j-1] + 2$ - $a[i]$ $!=$ $b[j]$ 此时又细分为两种情况
- 不处理，有
$dp[i][j] = dp[i-1][j-1]$ - 处理，即在 $a_1… a_i$ 或 $b_1 … b_j$ 中位置 $k$ 处添加空格
$dp[i][j] = dp[k][j] - 1$
$dp[i][j] = dp[i][k] - 1$
- 不处理，有
T43121 任务安排（Batch）
$n = 5000$ ，复杂度最大为 $O (N^2)$
参考
设：
※ dp[i] 表示前 i 个任务的最小费用
※ w[i] 表示前 i 个任务费用系数的前缀和
※ t[i] 表示前 i 个任务需要单调时间的前缀和
推导递推式的过程中会发现，分组时的开机时间 s 会产生后效性
为了解决后效性问题，在循环 j-i 时（表示 j-i 分一组），需要将对后面所有任务产生的部分费用一起累加
于是可以得到状态转移方程
dp[i] = max { dp[j-1] + s * (w[n] - w[j-1]) + (w[i] - w[j-1]) * t[i] }
T43122 最大的算式（Bigexp）
数据范围较小，可以考虑复杂度较大的算法
$dp[i][j][num]$ 表示区间 $[i, j]$ 内有 $num$ 个乘号时的最大结果
由小区间向大区间$DP$（无后效性，也就是对之后的结果没有影响）
设 $q$ 为断点， $m$ 为左子区间的乘号数量，考虑 $q$ 的符号问题：
- 断点 $q$ 不为乘号
$dp[i][j][k] = dp[i][q][m] + dp[q+1][j][k-m]$ - 断点 $q$ 为乘号
$dp[i][j][k] = dp[i][q][m] * dp[q+1][j][k-m-1]$
T43123 字符距离BLAST
数据范围较大， 复杂度最大为 $O (N^2)$
$ dp[i][j] $ 表示处理到两字符串 $a_i, b_j$ 位置
此时有两种选择：
- 不插入空格
即直接计算距离 $dp[i][j] = dp[i-1][j-1] + dis(a_i, b_j)$ - 插入空格到 $a_i$ 或是 $b_j$ 位置
此时前面未插入空格的部分仍然匹配，只需考虑最后一位
$dp[i][j] = min (dp[i-1][j] + k, dp[i][j-1] + k)$
另外，初始化时 $dp[i][0]$或 $dp[0][j]$直接考虑为：
空字符串与 $a_1 … a_i , b_1 … b_j $ 匹配，即全部用空格填充
//初始：一方为空，另一全用空格构造
if (i == 0)
dp[0][j] = k * j;
else
if (j == 0)
dp[i][0] = k * i;
T43142 公路乘车（Busses）
呜呜呜~ ~，终于看见一道水题了
咳咳，首先求出每种的性价比，然很根据性价比排序，再逐一选择…
好吧，其实本题就是一个背包问题
$dp[i]$ 表示价格为 $i$ 的最小花费，再枚举每种路程的花费
$dp[i] = min (dp[i], dp[i-j] + p[j])$
代码
T43144 积木城堡（Castle）
上限 $100$ 个城堡，$100$ 个积木，$100$ 的棱长，也就是说，$O (N^3)$ 复杂度可取
考虑读入每个城堡后利用背包问题的原理将每个城堡可以搭成的高度全部枚举并计数，最后再总高到低遍历求解
代码
T43145 筷子（Chop）
分析题意，由于为使“每双的筷子长度差的平方和最小”，由贪心策略可得，将筷子按长度排序后，选取的每对筷子一定是相邻的
因而首先将筷子按长度排序，再进行 $DP$
$ dp[i][j] $表示前 $i$ 支筷子中 ，取 $j$ 双筷子的最小长度差平方和，有
- 选第 $i, i-1$ 支筷子
$dp[i][j] = dp[i-2][j-1]$ - 不选第 $i, i-1$ 支筷子
$dp[i][j] = dp[i-1][j]$
代码
T43146 护卫队（Convoy）
在说这道题之前，请容许我吐槽一句：
数据是真的坑 泪流满面
我也很无奈啊，怎么会有这种鬼数据 呜哇哇
好了，进入正题，首先注意题目，是单行道，也就是说改顺序什么的是不存在的
$dp[i]$ 表示通过前 $i$ 辆车所需的最短时间
通过枚举右端点向左找最大的区间，其间每个点都可作为最后一个区间（指的是到 $i$ 为止的）的左端点，再根据这个 $DP$
设 $slowest$ 是最后一个区间 $[l, r]$ 中走的最慢的一辆车的时间，有
$dp[r] = min (dp[r], dp[l-1] + slowest) $
代码
T43147 对话（Dialog）
又是一道毒瘤题qaq
思路很简单，还是以背包问题的写法，判断一遍存在性（是否可到达），比较部分可以如下处理
// a 串中 l - r 段 与 b 相同 （可以用 substr）
bool check (int l, int r, string a, string b)
{
int L = r - l;
/* string q = a.substr(l, L+1);
return q == b;*/
for (int i = 0; i <= L; i ++)
if (a[l + i] != b[i])
return false;
return true;
}
而个人认为本题最坑的地方在于，，没错，还是数据，，
哇，简直，，，忍无可忍，，说好的长度$200$呢？$10002$是什么意思qaq
对此，还有一个小优化，因为总共只有 $6$ 种单词，最长长度也不超过 $6$， 所以如果出现连续长度为 $6$ 的区间， $vis$ 都为 $0$，可以提前结束判断
for (int i = 1; i <= ls; i++)
{
if (...)
{
......
}
S[i] = S[i-1] + vis[i];//前缀和数组
if (i > 7)//小优化
{
if (S[i] - S[i-7] == 0)
return false;
}
}
不说了，气死了，，，
代码
T43148 美元DOLLARS
终于有相比于某些毒瘤题简单点的题目了，呜呜~ ~
对于每天的钱数，我们考虑两种操作：
如果将美元兑换为马克是赚的，我们将所有美元兑换为马克
如果将马克兑换为美元是赚的，我们将所有马克兑换为美元
$f[i][0]$ 表示第 $i$ 天美元最大值， $f[i][1]$ 表示第 $i$ 天马克最大值
对于每一次操作，将之前马克/美元最多的一天兑换
代码
