Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

此题虽水,但我人更水。在此非常感谢winsweet 师兄。

Posted by denghongchao at 2009-08-12 23:12:20 on Problem 1651 and last updated at 2009-08-12 23:13:25
这道题其实非常的好,考察一个人对矩阵的掌握程度。不会做的回去看《高等代数》。
我的理解是把相邻的两个数看作矩阵的长宽。例如矩阵 a1 * a2 ,a2 *a3.....an-1 * an;
两个矩阵相乘 ,有:(n×m)*(m×p)变成 n×p的矩阵。这样就把m  取掉了。
对 a[i,j]为c[i] ×c[j+1] 的矩阵。这样a[1,n-1]就为 第一个数乘以最后一个数了c[1]*c[n]。
取其中的一个k.假设最小。 a[i,k] + a[k+1, j] + c[i]*c[k+1]*c[j+1];
a[i,k] 和 a[k+1,j] 分别是最优解.他们合并为a[i,j]的时候去掉了c[k+1].代价是c[i]*c[k+1]*c[j+1];
a[i,k] 和 a[k+1,j]  易证得分别为最优子结构,相互独立。
好难想。可能是我太水了。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator