【TYVJ P1014】乘法游戏
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
太原成成中学第2次模拟赛第四道
描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。
你的目标是使得分的和最小。
例如，如果数是10150205，依次拿1、20、50，总分是10*1*50+50*20*5+10*50*5=8000
而拿50、20、1，总分是1*50*20+1*20*5+10*1*5=1150。
你的目标是使得分的和最小。
例如，如果数是10150205，依次拿1、20、50，总分是10*1*50+50*20*5+10*50*5=8000
而拿50、20、1，总分是1*50*20+1*20*5+10*1*5=1150。
输入格式
输入文件的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。
输出格式
输出文件只有一个数字：最小得分
测试样例1
输入
6
10 1 50 50 20 5
输出
3650
TYVJ的评测机不行了。搞得我得下测试数据。
这道题明显是一道动态规划题，而且是区间动规。那么怎么建立状态转移。
首先我们很容易想到，大区间都是由小区间推出来的，那么就会存在最优子结构。
然后，无论小区间怎么样都无法影响大区间的答案。那么状态转移方程就呼之欲出了。
设f[1][n - 2]是答案。
f[i][j] = min{f[i][k - 1] + f[k + 1][j] + a[i - 1] * a[k] * a[j + 1] | i < k < j}
但是呢，我们得先预处理出f[i][i]和f[i][i + 1]的答案并且把f[i][j] | j < i 的值设为0。
1、统计字符串中各个字符出现的次数
2、牛客练习赛17
3、笔试题之数据结构
4、您安心的走吧——5.17晚一夜天降小雨祭文 （献给爸爸，祭文，之三）
5、saiku 展示优化
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstdlib> 6 using namespace std; 7 8 long long f[105][105]; 9 int a[105]; 10 int n; 11 12 int main() 13 { 14 scanf("%d", &n); 15 for (int i = 0; i < n; ++i) 16 scanf("%d", &a[i]); 17 memset(f, 0x7f, sizeof(f)); 18 f[0][0] = f[n - 1][n - 1] = 0; 19 for (int i = 1; i < n - 1; ++i) f[i][i] = a[i - 1] * a[i] * a[i + 1]; 20 for (int i = 1; i < n - 2; ++i) 21 f[i][i + 1] = min(f[i][i] + f[i + 1][i + 1] / a[i] * a[i - 1], f[i + 1][i + 1] + f[i][i] / a[i + 1] * a[i + 2]); 22 for (int i = 1; i < n; ++i) 23 for (int j = 0; j < i; ++j) 24 f[i][j] = 0; 25 for (int i = n - 2; i > 0; --i) 26 for (int j = i + 1; j < n - 1; ++j) 27 for (int k = i; k <= j; ++k) 28 f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[i - 1] * a[k] * a[j + 1]); 29 cout << f[1][n - 2] << endl; 30 //system("pause"); 31 return 0; 32 }优质内容筛选与推荐>>
1、统计字符串中各个字符出现的次数
2、牛客练习赛17
3、笔试题之数据结构
4、您安心的走吧——5.17晚一夜天降小雨祭文 （献给爸爸，祭文，之三）
5、saiku 展示优化