Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1651 矩阵连乘

Posted on 2010-08-26 21:38 Onway 阅读(811) 评论(0)  编辑 收藏 引用 所属分类: 伤不起的ACM
 

pku 1651 Multiplication Puzzle

题意:给出一组N个数,每次从中抽出一个数(第一和最后一个不能抽),该次的得分即为抽出的数与相邻两个数的乘积。直到只剩下首尾两个数为止。问最小得分是多少。

最优子结构:

假设总得分最小时最后抽出的数在k位置,则在1:k和k:n之间的得分也是最小的。因为如果1:k或者k:n具有更小得分,则总得分会更小,与假设矛盾。

状态设计:

设dp[i][j]为第i个数到第j个数的最小得分,则dp[1][n]即为题中的解。

1<=i<=n-2;i+2<=j<=n;

 

dp方程:

dp[i][j]=min(dp[i][k]+dp[k][j]+s[i]*s[k]*s[j]);i<k<j;

观察方程,第一维中依赖的是i以后的值,第二维依赖的是j之前的值,所以第一维循环采用逆序循环,第二维采用顺序循环。

 
Memory: 756K Time: 0MS
Language: G++ Result: Accepted

#include <iostream>
#include 
<stdio.h>
#include 
<cstring>
using namespace std;
int dp[103][103],s[103];
int main()
{
    
int n,i,j,k,min;
    scanf(
"%d",&n);
    
for(i=1;i<=n;++i)
        scanf(
"%d",&s[i]);     
    memset(dp,
0,sizeof(dp));
    
for(i=n-2;i>=1;--i)
        
for(j=i+2;j<=n;++j)
        {
            min
=i+1;
            
for(k=i+2;k<=j-1;++k)
                
if((dp[i][k]+dp[k][j]+s[i]*s[j]*s[k])<(dp[i][min]+dp[min][j]+
                    s[i]
*s[j]*s[min]))
                        min
=k;
            dp[i][j]
=dp[i][min]+dp[min][j]+s[i]*s[j]*s[min];   
        }
    cout
<<dp[1][n]<<endl;
    
return 0;
}


这个题目折腾了我很久,估计也有五六个小时。可能是太久(也快半个月了)没做过题,也可能是对矩阵连乘这类DP,或者直接是对DP没有更深入的理解(其实真正领悟DP又何尝简单?可以原谅)。其实矩阵连乘,在前几天才看了第二遍,当时没看书上的代码,认为对于DP看方程看代码其实是没多少意思的,重要的是那个思路,问题的分析,子结构的证明,然后自己写方程写代码。

我是百度矩阵连乘搜到这个题目的,所以这个题目的方法一开始就知道。最先自己简单的分析了一下子结构,然后找了个方程就开始写递归,结果调试就卡住了。然后没用递归,用数组,用堆栈又写了两次,发现都是卡在了同一个地方。

后来怀疑起子结构和方程,原来对子结构没有搞清楚,写出的方程也错的很不靠谱。待我通过了这个题后,看回自己的DP方程,发现兜了一大圈,还真是回到了矩阵连乘这里。

对于一个方法已经知道,类型也见过的题目,总是有一点轻视,加之对原来了解的就不深入,犯错就很容易理解了。

 

最后说说编程上的知识:

1, memset,strlen等字符串处理函数在G++要用到<cstring>头文件

2, scanf,printf要用到<stdio.h>头文件

3, ;abs在<cstdlib>中;fabs,sin,sqrt等数学函数在<cmath>中


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理