大体题意：
一个n*m的矩阵由n行m列共n*m排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个n*m的矩阵乘m*p的矩阵，运算量为n*m*p。
矩阵乘法不满足分配律，但满足结合律。因此A*B*C既可以按顺序（A*B）*C也可以按A*（B*C）来进行。假设A、B、C分别是2*3、3*4、4*5的，则（A*B）*C运算量是2*3*4+2*4*5=64，A*（B*C）的运算量是3*4*5*2*3*5=90.显然第一种顺序节省运算量。
给出n个矩阵组成的序列，设计一种方法把他们依次乘起来，使得总的运算量尽量小。假设第i个矩阵A[i]是P[i-1]*P[i]的。
思路：
记忆化搜索：
令dp[i][j]表示从第i 个矩阵 一直乘以到 第j 个矩阵的最优解！
那么我们直接枚举中间的乘号 k，
转移方程就是 dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k] *p[j]}
假设第i个矩阵式是p[i-1] * p[i]；
边界式 dp[i][i] = 0;
详细见代码：
#include
#include
#include
using namespace std;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn];
int dp[maxn][maxn];
int dfs(int l,int r){
int& ans = dp[l][r];
if (ans != -1)return ans;
if (l == r)return ans = 0;
if (l+1 == r){
return ans = a[l-1]*a[l]*a[r];
}
ans = inf;
for (int k = l; k /**
4
2 3 4 5
ans = 64
3
2 3 4
ans = 24
4
10 100 5 50
ans = 7500
7
30 35 15 5 10 20 25
ans = 15125
**/|
Multiplication Puzzle Description The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row. The goal is to take cards in such order as to minimize the total number of scored points. For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring Input The first line of the input contains the number of cards N (3 Output Output must contain a single integer – the minimal score. Sample Input 610 1 50 50 20 5 Sample Output 3650 Source Northeastern Europe 2001, Far-Eastern Subregion |
|
Time Limit: 1000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 8763 |
|
Accepted: 5486 |
[Submit] [Go Back] [Status] [Discuss]
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
想知道由4.2号到4.9号之间移动应用市场究竟发生了什么变化？有哪些应用由默默无名变为榜上有名？又有哪些应用从被榜上被刷下来？那么就记得关注本周的榜单变化概述，你就清楚移动应用市场又有什么新趋势了。 以下榜单中出现的数据，来源于Appannie中Top Gro…
