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！！
