1006

news/2024/10/30 9:32:05/
背景 Background
    在很久很久以前,有一个动物村庄,那里是猪的乐园(^_^),村民们勤劳、勇敢、善良、团结…… 
   不过有一天,最小的小小猪生病了,而这种病是极其罕见的,因此大家都没有储存这种药物。所以晴天小猪自告奋勇,要去采取这种药草。于是,晴天小猪的传奇故事便由此展开…… 
 描述 Description
    这一天,他来到了一座深山的山脚下,因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂,由于小小猪的病情,晴天小猪想找一条需时最少的路到达山顶,但现在它一头雾水,所以向你求助。 
   山用一个三角形表示,从山顶依次向下有1段、2段、3段等山路,每一段用一个数字T(1<=T<=100)表示,代表晴天小猪在这一段山路上需要爬的时间,每一次它都可以朝左、右、左上、右上四个方向走(**注意**:在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段)。 
   晴天小猪从山的左下角出发,目的地为山顶,即隐者的小屋。
 输入格式 Input Format
    第一行有一个数n(2<=n<=1000),表示山的高度。 
   从第二行至第n+1行,第i+1行有i个数,每个数表示晴天小猪在这一段山路上需要爬的时间。
 输出格式 Output Format
    一个数,即晴天小猪所需要的最短时间。

也是一个动态规划的问题,但是自己对于动态规划的理解还是不够,各种窘迫,又一次不得不去参看别人的代码,由于自己水平比较低下,好多别人的代码都理解不了, 有些效率高的代码设计的很精巧,理解起来也极为困难,与之相对,一些容易理解的代码的效率也就不是很高了。最后自己找了一个暴力DP的思想来求解这个问题,期间的问题也是多多,各种被卡,直到很晚,才在博客园一位大牛的博客的启发下修改正确,这个问题将会着重讨论。动态规划啊,啥时候能有点感觉啊……

仍然无耻的把自己的代码贴出来。

#include <stdio.h>
//#include <Windows.h>
int a[1001][1001];
long int step[1001][1001];
int main()
{
int n,i,j,flag = 0;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
step[i][j] = 100000;
}
}
step[1][0] = a[1][1];
step[1][2] = a[1][1];
for (i=2;i<=n;i++)
{
while(1)
{	
step[i][0] = step[i][i];
step[i][i+1] = step[i][1];
flag = 1;
for (j=1;j<=i;j++)
{
//
if (step[i][j]>step[i-1][j]+a[i][j])
{
step[i][j] = step[i-1][j]+a[i][j];
flag = 0;
}
if (step[i][j]>step[i-1][j-1]+a[i][j])
{
step[i][j] = step[i-1][j-1]+a[i][j];
flag = 0;
}
if (step[i][j]>step[i][j-1]+a[i][j])
{
step[i][j] = step[i][j-1]+a[i][j];
flag = 0;
}
if (step[i][j]>step[i][j+1]+a[i][j])
{
step[i][j] = step[i][j+1]+a[i][j];
flag = 0;
}
}
if (flag == 1)
break;
}
}
printf("%ld",step[n][1]);
//system("pause");
return 0;
}
备注:

  1. 首先就是对于题意的理解出现了问题,题目表述不清楚,走的四个方向就把我整晕了,左右好理解,左上右上是啥回事,后来才想明白是三角锥形的排列方式,如下图,每行数据还是圆形排列,就像一个圆锥。
     
    本题可以采用自上而下或者自下而上两种方式来求解,我们采用自上而下的方式。根据上图的排列我们可构造出动态规划方程
    step[i][j] = min{step[i][j-1]+a[i][j],step[i][j+1]+a[i][j],step[i-1][j-1]+a[i][j],step[i][j]+a[i][j]}
  2. 在程序实现的过程中一再的报错,提示stack overflow,昨天的青蛙过河是由于递归层次太多导致堆栈溢出,这个程序也没有10^9这么大的数据,递归也没有用到,问题最后归结到了开篇那个数组身上,一开始将其声明为局部变量,后来改为全局变量程序才得以通过。原来windows32位操作系统给程序的栈、堆分配的空间默认为1M。我开辟的数组为step[1000][1000],假设为int类型的话,step占空间为4*1000*1000Byte 大约是3M多一点。出现越界也是必然的了。关于这个问题将会细致的讨论一下。参见文章程序中关于堆栈的划定。
    总结:在写程序的时候要有空间观念,大小超过1M的变量尽量定义为全局变量或者静态变量。


 
 

http://www.ppmy.cn/news/424936.html

相关文章

lytest01010101

python 一、print()函数的语法如下&#xff1a;   print(*objects, sep , end\n, filesys.stdout, flushFalse)   将 "objects" 打印输出至 "file参数" 指定的文本流&#xff0c;以 "sep 参数"分隔开并在末尾加上 "end参数"。 &q…

UVA1606

极角&#xff0c;扫描。 黑白点等价转换。 关键就是扫描这一小段。 int L 0, R 0; int cnt 2; // 分割线上的两个点 while( L<k ) {if( LR ) { R (R1)%k; cnt; }while( L!R&&Left( p[L],p[R] ) ) { R (R1)%k; cnt; }--cnt;L;ans max( ans,cnt ); } 这里怎么扫…

NO.15——使用Appium自动化测试爬取微信朋友圈数据

一、解析过程 本人使用锤子手机做测试&#xff0c;型号是YQ601&#xff0c;首先打开开发者模式确保手机能与mac相连&#xff0c;打开Appium客户端&#xff0c;配置参数如图 可以理解为Appuim继承自web端的selenium&#xff0c;同样可以执行一些自动化操作。Appium自带了一个XP…

xv6 6.S081 Lab8: fs

xv6 6.S081 Lab8: fs 写在前面实验介绍开始&#xff01;Large FileSymbolic links fs代码在这里。我的妈呀&#xff0c;终于要写完了&#xff0c;xv6的file system考察难度并不大&#xff0c;这里强烈推荐我工Ext2 Based File System&#xff0c;这里可以给一下参考代码与参考结…

Walllys/DR6018-S IPQ6010/IPQ6018/IPQ6000

Walllys/DR6018-S IPQ6010/IPQ6018/IPQ6000 Quad-core ARM 64bit A53 1.8GHz Processor Support OpenWRT, Support:QCN9074 WiFi Card Support OpenWRT  IPQ6010  802.11ax  2x2 2.4G&5G  DR6018-S IPQ6010/IPQ6018/IPQ6000 Quad-core ARM 64bit A53 1.8GHz Processor…

Android 视频 美颜SDK对比

Android 视频 美颜小结 美颜SDK美颜的本质Android 视频 美颜SDK对比 美颜SDK 蓝色AR 优点&#xff1a;文档规范 技术支持及时 价格适中 缺点&#xff1a;问题较多 包集成偏大 涂图 特点&#xff1a;前YY团队成员&#xff0c;10W 优点&#xff1a; 缺点&#xff1a; 商汤 特点…

YY/T 9706.106-2021医用电气设备 第1-6部分:基本安全和基本性能的通用要求 并列标准:可用性

目录 一、YY/T 9706.106-2021替换YY/T 1474-2016 二、YY/T 9706.106-2021医用电气设备 第1-6部分&#xff1a;基本安全和基本性能的通用要求 并列标准&#xff1a;可用性 IEC60601-1-6:2013 MOD 三、YY/T 1474-2016医疗器械可用性工程对医疗器械的应用&#xff0c;YY/T 1…

INSTALL_FAILED_SHARED_USER_INCOMPATIBLE错误解决

调试程序时项目设置了UID&#xff0c;使用不同的签名出现 Target device: smartisan-yq601-3fa1a5dc Installing APK: /Users/wangliang/workspace/emm-android/build/outputs/apk/emm-android-debug.apk Uploading file to: /data/local/tmp/com.xxx.vvv Installing com.poly…