HDU4283 You Are the One（Feb. 3rd, 2019） 区间DP

动态规划

$\color{teal}{\frak{La \ pluie\ told\ me\ to\ be\ serious.}}$

题目来源

题意

给定$n\in[1,100]$个带权$v_i$的点。最开始按照$1$至$n$标号顺序排列，可以用栈调整输出顺序。设第$i$个点第$k_i$个输出，求$(\sum v_i\times k_i)_{min}$。

原理

区间$DP$。$dp[i][j]$表示区间$[i,j]$中的点全部输出的最小花费。
初值：当$[i+1,j]$中的点按原顺序输出，$dp[i][j]=\bigg(\sum\limits_{x=i+1}^{j}a[x]\bigg)+dp[i+1][j]$，然后再来摆放第$i$个点的位置。注意：此处只考虑区间$[i,j]$，与前后无关。
转移：
枚举区间长度$l$｛
$\qquad$枚举区间左端点$i$｛
$\qquad\qquad$计算区间右端点$j$；
$\qquad\qquad$枚举区间断点$k$（即原本第$i$个输出的点后调到第$k$个输出）｛
$\qquad\qquad\qquad$直接按照题意计算后调后的值，和$dp[i][j]$比较更新，
$\qquad\qquad\qquad$即$dp[i][j]=min(dp[i][j],dp[i+1][k]+a[i]\times (k - i)+dp[k + 1][j] + \bigg(\sum\limits_{x=k+1}^{j}a[x]\bigg)\times (k-i+1))$。
$\qquad\qquad\qquad\bigg(\sum\limits_{x=k+1}^{j}a[x]\bigg)\times (k-i+1)$是因为无论区间$[k+1,j]$中的人的顺序怎么换，所有人都需要多等待区间$[i,k]$中的人出去，这是原本计算$dp[k+1][j]$时没有考虑到的。
$\qquad\qquad$｝
$\qquad$｝
｝
优化：其中连续求和可以预处理。
答案：$dp[1][n]$。
数据范围估计：最坏情况答案为$\sum\limits_{x=1}^{100}100x=100\times\frac{100\times 101}{2}<100^3=10^6$，不会爆$int$。

反思

$1.$区间$DP$思想：以短求长，以子区间$DP$值推导当前区间$DP$值。
$2. DP$合并答案时要注意$DP$值的定义（是否需要做调整）。

代码