加载中…
个人资料
abentu
abentu
  • 博客等级:
  • 博客积分:0
  • 博客访问:16,180
  • 关注人气:4
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

poj1651-Multiplication Puzzle

(2010-07-15 13:37:00)
标签:

杂谈

    这道题还是比较有意思的,题目是说让你在一个长度超过3的数列里依次删除一些数,不能从两边删除。而且每次删除的时候需要算一次它与两旁的数的三连乘积然后累加,直到整个数列只剩两个数,这样就得到了一些乘积的和,题目要求找到最小的乘积和。

    乍看上去不好下手,因为很难单独通过数学方法找到一种删除方法。而如果把这道题倒过来看,每次向这个数列里面添加数的话,就会拿到这样的模型:首先向两个数a,c中间加上一个数b,然后剩下的数字只能加到a,b中间或者b,c中间,这样,就得到了一个动态规划的策略,转移方程为:dp[a][c] = dp[a][b] + dp[b][c] + s[a]*a[b]*s[c],如果在a和c中间遍历b,就可以得到dp[a][c]的值。

    首先对最小的数列段找dp的值,然后扩展到最长的即可。

 

代码:

 

#include "stdio.h"
#include "memory.h"
#define N 110

int n,a[N],dp[N][N];

int main()
{
 freopen("3.txt","r",stdin);
 
 int i,j,k;
 while (scanf("%d",&n) != EOF && n >= 3)
 {
  memset(a,0,sizeof(a));
  memset(dp,0,sizeof(dp));
  for (i = 1;i <= n;i ++)
   scanf("%d",a+i);
  for (k = 1;k <= n-1;k ++)
  for (i = 1;i <= n-k;i ++)
  {
   if (k == 1)
    dp[i][i+k] = 0;
   else
   {
    dp[i][i+k] = 100000000;
    for (j = i+1;j <= i+k-1;j ++)
    if (dp[i][i+k] > dp[i][j] + dp[j][i+k] + a[i] * a[j] * a[i+k])
     dp[i][i+k] = dp[i][j] + dp[j][i+k] + a[i] * a[j] * a[i+k];
   }
  }
  printf("%d\n",dp[1][n]);
  n = 0;
  
 }

 return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有