建筑公司网站源码 开源 免费,手机版html编辑软件,中国知名企业排行榜,连云港建设局网站矩阵链相乘{\color{Cyan} 矩阵链相乘 }矩阵链相乘
Description
Input
n表示矩阵的个数(100)
n1个数,表示矩阵(100)
Output
最小的乘法次数
Sample Input
5
5 10 4 6 10 2
Sample Output
348
题目大意#xff1a;
有n个矩阵#xff0c;输入n1个数#x…矩阵链相乘{\color{Cyan} 矩阵链相乘 }矩阵链相乘
Description
Input
n表示矩阵的个数(100)
n1个数,表示矩阵(100)
Output
最小的乘法次数
Sample Input
5
5 10 4 6 10 2
Sample Output
348
题目大意
有n个矩阵输入n1个数第i个矩阵的行列分别为第i和第i1个数将他们合并在一起合并的时间为前面的矩阵的行×前面的矩阵的列/后面的矩阵的行×后面的矩阵的列要使他们合并成一对的时间最少
解题方法
这道题大体和石子合并ssl 2863)相同至少我这么认为,但他合并的代价为前面的矩阵的行数×前面的矩阵的列数/后面的矩阵的行数×后面的矩阵的列数并且输入多了一个数,
未做过石子合并的“大佬”看此
我们先枚举合成矩阵的个数(len)再枚举矩阵的第一个(i)最后一个(j)就出来了最后枚举分割线(k)用分割线前面矩阵花费的时间加上后面矩阵花费的时间最后加上a[i]×a[k]×a[j1] (因为是最后一个矩阵的列{\color{Red}列}列所以还要加1)
动态转移方程
f[i][j]min{f[i][j]f[i][k−1]f[k][j]a[i]∗a[k]∗a[j1]f[i][j]min\left\{\begin{matrix}f[i][j]\\ f[i][k-1]f[k][j]a[i]*a[k]*a[j1]\end{matrix}\right.f[i][j]min{f[i][j]f[i][k−1]f[k][j]a[i]∗a[k]∗a[j1]
#includecstdio
#includeiostream
#includecstring
#includealgorithm
using namespace std;
int f[105][105],a[105],n,j;
int main()
{memset(f,127/3,sizeof(f));//因为要求最小所以要先赋一个大的值scanf(%d,n);for (int i1;in1;i)//n要加1{scanf(%d,a[i]);f[i][i]0;//把只有一个矩阵的清零}for (int i1;in-1;i)//2因为只有两个矩阵所以可以特殊处理(更快)f[i][i1]a[i]*a[i1]*a[i2];for (int len3;lenn;len)//长度for (int i1;in-len1;i)//前面的矩阵{jilen-1;//后面的矩阵for (int ki1;kj;k)f[i][j]min(f[i][j],f[i][k-1]f[k][j]a[i]*a[k]*a[j1]);//动态转移方程}printf(%d,f[1][n]);
}能量项链{\color{Blue} 能量项链 }能量项链
Description
在Mars星球上每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子这些标记对应着某个正整数。并且对于相邻的两颗珠子前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样通过吸盘吸盘是Mars人吸收能量的一种器官的作用这两颗珠子才能聚合成一颗珠子同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m尾标记为r后一颗能量珠的头标记为r尾标记为n则聚合后释放的能量为Mars单位新产生的珠子的头标记为m尾标记为n。
需要时Mars人就用吸盘夹住相邻的两颗珠子通过聚合得到能量直到项链上只剩下一颗珠子为止。显然不同的聚合顺序得到的总能量是不同的请你设计一个聚合顺序使一串项链释放出的总能量最大。
例如设N44颗珠子的头标记与尾标记依次为(23) (35) (510) (102)。我们用记号⊕表示两颗珠子的聚合操作(j⊕k)表示第jk两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为
(4⊕1)102360。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕31023103510510710。
Input
输入的第一行是一个正整数N4≤N≤100表示项链上珠子的个数。第二行是N个用空格隔开的正整数所有的数均不超过1000。第i个数为第i颗珠子的头标记1≤i≤N当i时第i颗珠子的尾标记应该等于第i1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。
Output
输出只有一行是一个正整数EE≤2.1*109为一个最优聚合顺序所释放的总能量。
Sample Input
4
2 3 5 10
Sample Output
710
题目大意
有n个矩阵。。。和上体叙述大体一致但它是一个环形输入n个数(a[1],a[2]…a[n])每个矩阵的行列为a[1]×a[2],a[2]×a[3]…a[n-1]×a[n],a[n]×a[1],因为它是一个环形所以只要是相邻的就可以合并要求最大的要求最大的{\color{Red}要求最大的要求最大的}要求最大的要求最大的要求最大的重要的事情说三遍{\color{Red}要求最大的重要的事情说三遍}要求最大的重要的事情说三遍。
解题方法
我们可以按下图存放a将1-42-53-64-7这一堆当作第一题做再从这些中求最大的但这样31重循环有80%的可能性TLE所以我们可以将他们放在一起做这样重复的就可以不做了详情请看程序 #includecstdio
#includeiostream
#includecstring
#includealgorithm
using namespace std;
int f[205][205],a[205],n,j,ans;
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,a[i]);a[in]a[i];//复制一遍}for (int i1;in*2-2;i)//要再加一个n因为n1到n*2是等于1到n的所以要加1n-1n-1n*2-2f[i][i1]a[i]*a[i1]*a[i2];//长度为2的提前做for (int len3;lenn;len)//一样for (int i1;in*2-len;i)//后面的也要求所以要加n,因为n1到n*2是等于1到n的所以要加1n-len1n-1n*2-len{jilen-1;//一样for (int ki1;kj;k)//一样f[i][j]max(f[i][j],f[i][k-1]f[k][j]a[i]*a[k]*a[j1]);//要求最大的}for (int i1;in;i)ansmax(ans,f[i][in-1]);//要从这些中找最大的printf(%d,ans);
}
