codevs 1966乘法游戏区间dp

1966 乘法游戏

** 时间限制: 1 s

** 空间限制: 128000 KB

** 题目等级 : 黄金 Gold

题解

题目描述 Description

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。　　你的目标是使得分的和最小。　　例如，如果数是10 1 50 20 5，依次拿1、20、50，总分是　　　　　　　　　　 10150+50205+10505=8000　　而拿50、20、1，总分是15020+1205+1015=1150。

输入描述 Input Description

输入文件的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。

输出描述 Output Description

输出文件只有一个数字：最小得分

样例输入 Sample Input

610 1 50 50 20 5

样例输出 Sample Output

3650

线型dp，比如什么什么子序列呀什么的，他们的状态都是可以由上一个加加减减一步一步递推来的，状态转移也挺好想，但看到这一题，就懵逼了，随便给个点，鬼知道他是由什么转移过来的，如果你的思维局限在这里，那么你想破脑袋也不会有什么结果。。。那么我们换个思维方式，我们不想单一的一个点，因为一个点的变换方式是有很多个的，我们想一想一段（也就是一个区间）的最优解，设这一段长度为L，我们最终要求的就是长度为n的那一段的最优解，那么怎么求这一个区间的最优解呢？设这个区间为i---j(以i开头，以j结尾)，则i---j中取一点k（i<k<j）,那i---j区间的最优解就是i--k区间的最优解加上k+1---j区间的最优解再加上合并这两个区间所需的代价（此题就是相乘呗。。），但是要i--j区间最优，所以要枚举k从i+1---j-1的所有情况，取最优的那一组。

在此题中我们可以一开始把区间长度为3的最优解初始化出来，就是三个数相乘呗，没有其他可能了，然后更新长度为4的，在利用长度为1 2 3 4 的来更新长度为5的，这是一个递推的过程。

好了说了这么多，下面就上代码喽！

#include<iostream>
#include<algorithm>
using namespace std;
int a[110], n, dp[110][110], ma = 9999999;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 2) {
        cout << "0";
        return 0;
    }
    for (int k = 3; k <= n; k++)//区间长度
        for (int i = 1; i <= n - k + 1; i++) {//区间起始点
            ma = 99999999;
            for (int j = i + 1; j <= i + k - 2; j++) {//区间中的那个被枚举的任意点
                dp[i][i + k - 1] = dp[i][j] + dp[j][i + k - 1] + (a[i] * a[i + k - 1] * a[j]);
                ma = ma < dp[i][i + k - 1] ? ma : dp[i][i + k - 1];//更新最优解
            }
            dp[i][i + k - 1] = ma;
        }
    cout << dp[1][n] << endl;//输出
    return 0;
}

谢谢，点个赞hh！！