Loading... > 区间DP属于线性DP的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区间DP中，一个状态由若干个且包含于它的的区间所代表的状态转移而来，因此区间DP的决策往往就是划分区间的方法。区间DP属于线性DP的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区间DP中，一个状态由若干个且包含于它的的区间所代表的状态转移而来，因此区间DP的决策往往就是划分区间的方法。 **区间DP基本思想** 先计算小区间的最优解，再通过小区间得到大区间的最优解。 ## 区间 区间简单来说就是一个数据范围，信息学中常用于表示数组下标的范围，一般只考虑整数。 **区间的表示** [l,r] 闭区间 (l,r) 开区间 [l,r) 左闭右开 (l,r] 左开右闭 ## 题解 抽卡牌 ### 描述 蒜头君手里有 n 张卡牌，编号从 1 到 n，每张卡牌上面有一个数字 $num_i$。现在蒜头君将 n张卡牌排成一行，组成一个序列，执行以下操作：从序列中抽取一张编号为 i 的卡牌，则该张卡牌贡献的得分为 $num_{i-1} * num_i * num_{i+1}$，即卡牌上的数字同左右两张相邻的卡牌上的数字乘积。但是不能抽取序列中最左边和最右边的卡牌，即 i≠1且 i≠n。抽到的卡牌就从序列中去掉。重复上述操作，直到序列里只剩两张卡牌。抽取的总得分为每次抽取的得分之和。 现在蒜头君想知道，怎么进行卡牌抽取，可以使得总得分最小。 ### 输入 第一行输入一个整数 n（3≤n≤100），表示一共有 n 张卡牌。 第二行输入 n 个整数 $num_i (1\leqslant num_i\leqslant 100)$ ### 输出 输出一行，输出一个整数，表示卡牌抽取的最小总得分。 ### 题解 每个区间可以划分为两个包含于它的区间，递归划分区间，每个大区间的最优解由两个包含于它的区间得到。 那么，怎么把区间划分为两个小区间呢？也就是说，怎么确定两个小区间的分界点呢？ 其实，只要每个分界点都搜索一遍就可以了。（没错，简单粗暴）注意，区间中最左和最右的卡牌不能被抽取，不能作为分界点。一个区间中只有最左和最右的卡牌了，那就回溯吧  在本题中，设k为(l,r)分界点，可列出状态转移方程 $$f[l][r] = \min(f[l][k] + f[k][r] + a[l]*a[k]*a[r])$$ 为什么是a[l]\*a[k]\*a[r]而不是a[k-1]\*a[k]*a[k+1]?（~~这个问题我想了好久才想通~~） 在人类的思维里，抽卡牌的过程是：选择卡牌、抽卡牌、累加得分 可电脑是先选择的分界点最后抽，即一个分界点在两边的小区间都“抽”完后才会被抽，此时此区间只剩3张卡牌：最左、分界点、最右。出现这个问题其实是对DP状态转移理解错了  ### 代码 ```cpp #include <iostream> using namespace std; int n, a[100], f[100][100]; int dp(int l, int r){ if(f[l][r]) return f[l][r]; if(r-l < 2) return 0; f[l][r] = 1e9; for(int k = l+1; k < r; ++k){ f[l][r] = min(f[l][r], dp(l, k)+dp(k, r)+a[l]*a[k]*a[r]); } return f[l][r]; } int main(){ cin >> n; for(int i = 0; i < n; ++i){ cin >> a[i]; } cout << dp(0, n-1) << endl; return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 赞赏作者 微信
