# HDU-4283 区间DP
## [HDU-4283](http://acm.hdu.edu.cn/showproblem.php?pid=4283)
## 题目描述
非诚勿扰, 男嘉宾上台选秀, 一人上台占用一时刻. 第$i$个人等待一时刻会产生$D[i]$屌丝值. 有一个黑房间先进后出, 导演可以用它来改变男嘉宾上台顺序. 求节目结束后最小总屌丝值和.
## 分析
房间本质是一个栈, 栈有自带的子结构性质: 最终的出栈队列, 一定是由入栈队列的一个或多个不定长**顺序/逆序**子队列组成的, 举几个例子:
- 如{1,2,3,4,5}以{1,2,5,4,3}出栈, 则这些子队列是: {1,2},{5,4,3}.
- 如{1,2,3,4,5}以{2,4,3,1,5}出栈, 则这些子队列是: {1},{2},{4,3},{5}.
- 如{1,2,3,4,5}以{5,4,3,2,1}出栈, 则这些子队列是: {5,4,3,2,1}.
- 因此, **出入栈本身的复杂情况, 可以被简化为完全顺序/完全逆序序列的任意合法排列**, 解题就转变成了一个枚举这些序列的过程.
---
进行孤立区间的划分. 划分选手编号区间$[i,j](1 \le i,j \le n)$:
- $i=j$ 时, 代价不论如何都是$0$(就一个人).
- $i+1=j$ 时, 最小代价是 $D[i]$ 和 $D[i+1]$ 中较小值.
- $i+2=j$ 时情况变得复杂, 枚举栈的可能情况, 得到最小代价是以下五项的最小值:
$
min\begin{cases}
2D[i] &+D[i+1], &&(1) \\
2D[i] &+D[i+2], &&(2) \\
2D[i+1] &+D[i+2], &&(3) \\
2D[i+2] &+D[i] , &&(4) \\
2D[i+2] &+D[i+1], &&(5)
\end{cases}
$
还有一项 $2D[i+1]+D[i]$ 不存在, 栈做不到. 不难看出, 各类情况都是由1:2这样的划分得出的。
- 划分为 $A = [i]$ 和 $B = [i+1,i+2]$ 时, 有:
- $A$先出$B$后出, 总代价为$A_{最小} + B_{最小} + B_{总体等待} \times len(A) => (3) \lor (5)$
- $B$先出$A$后出, 总代价为$B_{最小} + A_{全逆序} + A_{总体等待} \times len(B) => (1) \lor (2)$
- 划分为 $A = [i,i+1]$ 和 $B = [i+2]$ 时, 有:
- $A$先出$B$后出, 总代价为$A_{最小} + B_{最小} + B_{总体等待} \times len(A) => (4) \lor (5)$
- $B$先出$A$后出, 总代价为$B_{最小} + A_{全逆序} + A_{总体等待} \times len(B) => (1)$
为什么$B$先$A$后中的$A$要取全逆序呢? 是因为想让$B$先出, 就必须让$A$全部进栈. 在这一事实下, $A$的最小代价就无关了.
因此, **一个区间的最优解一定唯一由其各个子区间的最优解和逆序边界解推导出**.
比较神奇的一件事. 这样的推导自动地避开了栈的不可能情况, 原因大概是推导本身就建立在栈的规则下, 没有越界.
最终结论: 在明确顺序/逆序排列组合性质的前提下, 我们分层讨论, 每层区间长度+1, 从1开始推到问题实际规模. 在每一层中再进行一次区间划分, 划分点从区间头到区间尾. 这种推法保证可以枚举到所有合法的顺序/逆序排列(从下至上, 每一层都枚举全, 则总体就是枚举全的, 而不需要在单层枚举全部情况, 这也是DP的核心思想之一).
## 状态转移方程
根据上述分析进行转移方程的推导.
设孤立区间$[i,j]$的**每时刻总体等待代价**为$wait[i][j]$
$$
wait[i][j] = \displaystyle \sum_{x=i}^j D[x] = wait[i][j-1]+D[j]
$$
设孤立区间$[i,j]$的**全逆序代价**为$rev[i][j]$
$$
rev[i][j] = \displaystyle \sum_{x=i}^{j} (j-x)D[x] = rev[i+1][j]+(j-i)D[i]
$$
设孤立区间$[i,j]$的**最小代价**为$dp[i][j]$
$$
\begin{align}
初始值:dp[i][j] &= rev[i][j], \\
递推值:dp[i][j] &= min\begin{cases}
dp[i][j] \\
dp[i][k] + dp[k+1][j] + (k-i+1)wait[k+1][j] \\
dp[k+1][j] + rev[i][k] + (j-k)wait[i][k]
\end{cases} , &&i \le k \lt j
\end{align}
$$
这里的递推完全来自于上面的分析. 注意整个区间都逆序时的情况($k=j$), 也可能是最优解. 这里为了编程方便, 可以设置其为初始值.
## 心得
**关键在于对栈的子结构性质的洞察**, 有了顺序/逆序的子结构, 区间DP就呼之欲出了.
## 代码
```cpp
// -------------- GLOBAL ----------------
int D[150];
LL dp[150][150], rev[150][150], wait[150][150];
// -------------- FUNC ----------------
// -------------- MAIN ----------------
int main() {
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
fill0(dp);
INI(n);
F1(i, n) {
scanf("%d", D + i);
}
F1R(i, n) {
for (int j = i; j <= n; ++j) {
wait[i][j] = wait[i][j - 1] + D[j];
}
for (int j = n; j >= i; --j) {
rev[i][j] = rev[i + 1][j] + (j - i) * D[i]; // 两个小dp
}
}
F1(l, n - 1) { // 区间长度为l
F1(i, n - l) {
int j = i + l;
dp[i][j] = rev[i][j];
for (int k = i; k < j; ++k) { // 以k为划分点
dp[i][j] = min(dp[i][j], min(dp[i][k] + dp[k + 1][j] + (k - i + 1) * wait[k + 1][j], dp[k + 1][j] + rev[i][k] + (j - k) * wait[i][k]));
}
}
}
printf("Case #%d: %lld\n", t, dp[1][n]);
}
return 0;
}
```
![]()