DP进阶训练：区间dp + 数位dp + 状压dp

vj题单

A. Multiplication Puzzle (区间dp)

题意：

• 首先这道题题意大概是：n个数字，每次你能拿走一个数字(除了两边的)，贡献是这个数字和两边两个数字的成绩。最后题目要求你按任意顺序拿走n-2个数字，使得贡献和最小。

分析：

• 顺序： 首先能想到是个dp题，因为在思考时候就是在考虑最优的处理顺序是什么。注意，这里提到了一个很关键的词：顺序，这表示一种策略，显然不能想到合适的贪心思路，那就往dp方向想。
• 性质： 我在最初思考时候，一般按照yxc dalao的闫式dp分析法，首先先认真分析这道题中存在的性质。(个人的一点看法：每个题不同的性质是解这道题的关键，如果你感觉没有思路，可能是没有抓住或挖掘出关键性质)。本题我认为关键的性质是：三个相邻的数要一同考虑，贡献是a[i - 1] * a[i] * a[i + 1]。三个数考虑的结果是a[i]从数组中删除。一个数组不断删除，会从长数组变成短数组，即若短数组最优解计算出来后，可以反着求出长数组的最优解。这个性质就已经指向了区间dp，因为前面的性质是在区间间转移。
• 表示： 通过前面分析，你得到了解题思路是dp, 关键性质是区间间的转移方式。接着就应该去思考如何通过dp数组来表示一个局面，或者说dp数组如何定义。误区，再以前做dp题时候我有个误区，就是没有特别看重题目性质分析这一步，这导致我经常在嗯想dp表示和转移。还有个误区就是我总是希望dp数组能表示一个局面，然后再不同的局面间进行dp转移。但事实上具体的局面很难表示这也是我做不出dp题的原因之一。如何去思考dp表示呢：一个很关键的词就是————抽象。试想一下动态规划问题就是在考虑一大堆子状态局面间的转移问题，但是状态表示和状态转移都十分不好想。但是我们有时候看题解会发现他们中状态转移非常丝滑，原因就是状态表示的好，使得两个状态间的转移非常清晰。所以要练习自己抽象的能力，因为好的状态表示它不是表示出一个具体的局面，比如本题中具体局面就是一种剩余数字的结果,如[10, 1, 50 ,5] 这种，我们会发现这怎么表示呀？？ 所以好的表示是把这道题涉及的子状态局面划分成多个抽象的集合，每个集合是许多小局面的组合，而这些集合间能有清晰的转移。具体见下图。本题相对简单，因为区间dp一般就是dp[l][r]，本题中表示l到r这个区间处理结束的最优解。
  
  
• 转移： 有了好的表示转移是不难的，更多时候表示和转移是放在一块考虑的，单考虑一个可能会让另一个的工作变得难做。本题中是dp[l][r]表示l到r之间处理结束， 那子状态如何贡献给dp[l][r]呢？这里有个关键词：完全覆盖 意思就是在考虑状态转移时要把所有能更新当前状态的子局面都考虑到。所以本题考虑l,r之间的k节点是当前[l,r]数组最后一个更新的，dp[l][r] = min{dp[l][k] + dp[k][r] + a[l] * a[r] * a[k]} dp[l][k] + dp[k][r] 就表示l到k间数字和k到r间数字都删除完的最优结果。我再一开始考虑时犯了个错误，我想的是dp[l][r] = min{dp[l][k] + dp[k + 1][r] + 更新最优值} 相当于我认为先把[l, k] 区间删到最后两个值，再把[k+1,r]删到最后两个值。这里其实犯的错误就是没有完全覆盖，因为我这么想相当于我把k+1留在了最后再考虑是否删除，但是对于[l,r]数组k+1它不是边界数字， 你甚至可以上来就把k+1这个数字删除了， 但我这样想相当于给加了一条限制(就是k+1这个数字留到最后删除)，使得原本更新[l,r]的子状态一部分状态因为不满足这个新加的限制，没有用于更新[l,r]状态，这就是没有完全覆盖。
• 整理一下思路：dp[i][j]表示数组[i,j]之间删除到只剩两边数字时的最优解，转移方程dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]) 表示[i,k],[k,j]两个数组都删除到只剩i,k和k,j的最优解的和，然后在[i,k,j]三个数的数组中删除k进行合并，贡献为a[i] * a[k] * a[j]。 初始化：[i,j]长度小于3的初始化为0， 等于3的初始化为 a[i] * a[i + 1] * a[i + 2], 大于3的初始化为INF(因为后面转移时取min)。 结果： dp[0][n - 1]

代码

# 省略头文件
int main() {
    // freopen("../temp.in", "r", stdin);
    // freopen("../temp.out", "w", stdout);
    int n; scanf("%d",&n);
    vector<int> a(n, 0);
    for(int i = 0; i < n; ++ i) {
        cin >> a[i];
    }
    vector<vector<int> > dp(n, vector<int>(n, 0x3f3f3f3f));

    for(int len = 1; len <= n; ++ len) {
        for(int i = 0; i + len - 1 < n; ++ i) {
            int j = i + len - 1;
            if(len < 3) {
                dp[i][j] = 0;
                continue;
            }
            if(len == 3) {
                dp[i][j] = a[i] * a[i + 1] * a[j];
                continue;
            }
            for(int k = i + 1; k < j; ++ k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}