那些我比赛未做出的DP题
此文为笔记，用于自我反思。
一、数据结构维护DP
1. div1-D Serious Business 【补题记录】
题意：一个矩阵有3行，n列，每个格子有收益:\(a_{i,j}\)可以小于0，要求你从(1,1)走到(3,n)，但是一开始row[2]是被封锁的，你需要花钱来解锁一些线段。你可以花\(k_i\)元来解锁\([l_i, r_i]\)，让你最大化你得到的收益.
解析
首先需要转换问题为DP模型。此题的难点在于后面如何转移DP。
预处理出3行的前缀和，那么我们选择\((l,r)\)的答案就是：\(sum(0, 1, l)+sum(1, l, r)+sum(2, r, n)\)
把变量中的l、r拆开，得到：\(F[l]=s[0][l]-s[1][l-1]\)、\(G[i]=sum(2, r, n)+s[1][r]\)，那么答案就是：\(F[l]+G[r]+cost(l,r)\)，其中\(cost(l,r)\)是选择解封的最小花费。
难点就在怎么计算cost函数，因为它即涉及变量l，又涉及变量r。或者说难点在于对于每个i:[1,n]，求出它的决策点（当时我就是这样想的，就G了。此题根本不是问求每个i的决策点，而是求全局最优解）。
正解：考虑只解封\([l,r]\)，那么答案就是：\(max(MAX\_F[l,mid]+MAX\_G[mid+1,r],ans[l,mid],ans[mid+1,r])\)。
好，一个块的答案我们解决了。
那么两个块呢？假设为：\([l_1,r_1]、[l_2,r_2] 且 l_2
那么\(ans=max(ans[l_1,r_1],ans[l_2,r_2], MAX\_F[l_1,r_1]-w_1+MAX\_G[r_1+1,r_2]w_2)\)
很理所当然地想到了吧，那么三个怎么办？四个怎么办？
我们从左往右做DP，当求出一个块\([l,r]\)的答案时，顺便拿\(MAX\_F[l,r]-w\)更新\(r_1\)处的权值，这部分用线段树处理。嗯，已经语无伦次了。
二、状态较难设计的DP
1.2022寒假训练 F.Fence Job
题意：你可以进行任意次操作，每次操作让[l,r]所有数字变成[l,r]区间内的最小值。求能形成多少种不同的数列。
解析
一开始就设计状态为：DP[i][j]为考虑前i位，以颜色j结尾的种数，转移的时候发现无法转移。
看题解发现，状态设计为：DP[i][j]为考虑前i为，以a[j]结尾的数量。
好处在于：j可以是大于i的，只要使用单调栈预处理出每个数字左侧小于他的位置，右侧小于它的位置即可。
转移的话，不需要考虑h[i-1]、h[i]之间的大小关系，只需要保证上一个块的id<=当前块的id即可。【这里我们从小到大枚举j进行保证，并利用前缀和优化】