| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 670 人关注过本帖
标题:动态规划
只看楼主 加入收藏
菜鸟,求帮忙
Rank: 4
等 级:业余侠客
帖 子:197
专家分:267
注 册:2015-7-11
结帖率:85.71%
收藏
已结贴  问题点数:36 回复次数:2 
动态规划
背景
在很久很久以前,有一个动物村庄,那里是猪的乐园(^_^),村民们勤劳、勇敢、善良、团结……
不过有一天,最小的小小猪生病了,而这种病是极其罕见的,因此大家都没有储存这种药物。所以晴天小猪自告奋勇,要去采取这种药草。于是,晴天小猪的传奇故事便由此展开……
描述
这一天,他来到了一座深山的山脚下,因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂,由于小小猪的病情,晴天小猪想找一条需时最少的路到达山顶,但现在它一头雾水,所以向你求助。
山用一个三角形表示,从山顶依次向下有1段、2段、3段等山路,每一段用一个数字T(1<=T<=100)表示,代表晴天小猪在这一段山路上需要爬的时间,每一次它都可以朝左、右、左上、右上四个方向走。山是环形的。(注意:在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段)。
晴天小猪从山的左下角出发,目的地为山顶,即隐者的小屋。
格式
输入格式

第一行有一个数n(2<=n<=1000),表示山的高度。
从第二行至第n+1行,第i+1行有i个数,每个数表示晴天小猪在这一段山路上需要爬的时间。
输出格式

一个数,即晴天小猪所需要的最短时间。
样例1
样例输入1[复制]

5
1
2 3
4 5 6










小弟望着这题欲哭无泪啊
这是俄的代码。。。。。。。。。一个都不过


#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("fin.in");
int f[1010][1010],g[1010][1010];
int main()
{
   int n;
       cin>>n;
   for(int i=1;i<=n;i++)
       for(int j=1;j<=i;j++)
       {
           cin>>f[i][j];
           g[i][j]=0;
       }           
       for(int i=2;i<=n;i++)
       {
           for(int j=1;j<=i;j++)
           {
               if(j==1)  g[i-1][i-1]>g[i-1][j+1]?g[i][j]=g[i-1][j+1]+f[i][j]:g[i][j]=g[i-1][i-1]+f[i][j];
               else       g[i-1][j-1]>g[i-1][j+1]?g[i][j]=g[i-1][j+1]+f[i][j]:g[i][j]=g[i-1][j-1]+f[i][j];
           }
         for(int j=1;j<=i;j++)
         {
             if(j==1)
             {
                if(g[i][j]>=g[i][i]+f[i][i])    g[i][j]=f[i][j]+g[i][i];
                  if (g[i][j]>=f[i][j]+g[i][1+j])     g[i][j]=f[i][j]+g[i][j+1];
             }
             else if(j==i)
             {
                 if(g[i][j]>g[i][i]+f[i][j-1])  g[i][j]=f[i][j]+g[i][j-1];
                  if(g[i][j]>f[i][j]+g[i][1])   g[i][j]=f[i][j]+g[i][1];
             }
             else
             {
               if(g[i][j]>f[i][j]+g[i][j-1])   g[i][j]=f[i][j]+g[i][j-1];
               if (g[i][j]>f[i][j]+g[i][i+1])   g[i][j]=f[i][j]+g[i][j+1];
              }
          }
       }
       cout<<g[n][1]+f[1][1];
//      system("pause");
}
搜索更多相关主题的帖子: 三角形 动态 传奇 动物 故事 
2015-08-01 18:45
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:18 
不太明白题意,楼主再举个例子吧

一片落叶掉进了回忆的流年。
2015-08-01 18:50
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
收藏
得分:18 
回复 楼主 菜鸟,求帮忙
楼主还需要再详述一下山的高度和层数的区别。这个有些看不明白。
如你举的例子
5
1
2 3
4 5 6
按你说法,山的高度是第一个数字5,下面又明显看来是三层,这是怎么回事?
2015-08-02 10:19
快速回复:动态规划
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.059216 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved