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大学生程序设计竞赛训练》暑期课面向全球招生!

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

Posted by 656766896 at 2012-02-29 21:09:12 on Problem 1651
In Reply To:此题虽水,但我人更水。在此非常感谢winsweet 师兄。 Posted by:denghongchao at 2009-08-12 23:12:20
> 这道题其实非常的好,考察一个人对矩阵的掌握程度。不会做的回去看《高等代数》。
> 我的理解是把相邻的两个数看作矩阵的长宽。例如矩阵 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