Posted on 2010-08-26 21:38
Onway 阅读(810)
评论(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>中