编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:   Password: 
 登记登记   
 不确定如何接近这个......
指数 -> 竞赛
转到页面 1, 2  下一页
查看上一个主题 可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题
作者 信息
SaltPro15




邮政发布: 2009年5月23日星期六上午10:37  发布主题:不确定如何接近...

大家好,

练习我的学校董事会的编程比赛,这是下周的,所以我正在做一些旧问题。我不确定如何接近这个。我在想DFS,但我忘记了它的结构 尴尬 这纯粹是为了个人使用,而不是学校任务,所以任何帮助/提示都会很棒。

问题c-2?为黄金旅行?
(保存在g:\编程竞赛\您的文件员作为QC2)
n x n array包含表示将在视频游戏中路径的交叉口收集的收费的值的数字。收费运营商不知道所有人的目的。负值表明收费守门员要支付这么多才能通过他。右侧的图表显示了可能的4 x 4阵列。

5 6 7 8
99 10 -100 -2
99 -100 -20 3
55 -16 7 8
角色从左侧进入网格(以其认为适当的行),并且必须遵循一些规则来右转。要搬到下一个地点,他可以移动南(下),北(上),东北,东部或东南部,但可能无法追溯他最近的举动。我们的角色应该在该示例中遵循大多数增加他的金(或花费)的路径描述(1,1) - (2,2) - (3,2) - (4,2) - (3 ,3) - (2,3)和(2,4),其中Co = inrinate表示网格中的行和列位置。沿这条路线支付的总额为5金+ 10金? 100金? 16金吗?20金? 100金?2金子?223
编写一个从文件C2.txt输入几行的程序。第一行是值n,n x n数组的大小。后续线是表示在每个N行中的每个N个交叉点处充电的收费的整数。输出应该是角色应该遵循的路径,并且在从右边出现时他将支付的收费。

到目前为止,我的代码和输入文件附加。基本上我现在所拥有的只是一种用于DFS和阵列和输入的类型



c2.txt.
 Description:

下载
 Filename:  C2.txt
 Filesize:  55 Bytes
 Downloaded:  212 Time(s)


C2.T.
 Description:

下载
 Filename:  C2.t
 Filesize:  346 Bytes
 Downloaded:  199 Time(s)

赞助
赞助
赞助
赞助
SaltPro15




邮政发布: 2009年5月23日星期六上午10:38  帖子主题:RE:不确定如何接近...

编辑:抱歉随机问号,我不确定为什么要在那里
A.J.




邮政发布: 2009年5月23日星期六10:55 AM  帖子主题:RE:不确定如何接近...

嘿saltpro15

很高兴有人终于在这个网站上发布了比赛问题 很高兴.

我的第一个问题是'n'的最大可能值是什么?

这是你需要知道的最重要的事实之一,好像n是微小的,直线递归应该足够快。

这个编程比赛是什么?有没有办法,我可以参加它吗? (随着比赛季节结束,我有点厌倦了Usaco,Topcoder是我现在唯一能做的事情......好吧,还有其他在线,如Spoj,但我宁愿做实际的比赛)
SaltPro15




邮政发布: 2009年5月23日星期六上午11:03  帖子主题:RE:不确定如何接近...

n应该不超过20

这只是我学校董事会的比赛,所以我认为你有点太远:对不起
SaltPro15




邮政发布: 2009年5月23日星期六11:13  帖子主题:RE:不确定如何接近...

实际上,我为什么不张贴整个小册子?如果有人无聊,这是我们在布洛克大学举行的地区学校董事会的比赛。它比其他比赛有点不太挑战,Con仍然被证明是挑战。今年是6月1日,如果除了我这里的其他人,idk除了我的关系,零效分是写作......


dsbn_contest.zip.
 Description:

下载
 Filename:  dsbn_contest.zip
 Filesize:  9.52 KB
 Downloaded:  1086 Time(s)

分析模式




邮政发布: 2009年5月23日星期六下午3:52  帖子主题:RE:不确定如何接近...

我会使用DP而不是递归。即使图表很小。

编辑:您没有给出n是什么。使用DP来避免收到TLE。
A.J.




邮政发布: 2009年5月23日星期六下午4:46  帖子主题:RE:不确定如何接近...

@Analysis mode - DP是可取的,真实的,但如果对于n的约束足够小,为什么会烦恼?与DP一起,回溯将更加困难(不大幅,但有点),因为他们希望您输出所采取的路径。
分析模式




邮政发布: 2009年5月23日星期六5:45 PM  帖子主题:RE:不确定如何接近...

不是真的,没有。

在真正的比赛中,将会给出界限,所以你可以做出选择。

这是经典的DP,为什么偏离?
赞助
赞助
赞助
赞助
SaltPro15




邮政发布: 2009年5月23日星期六晚上7:51  帖子主题:RE:不确定如何接近...

好的。分析模式,你认为你可以给我一个使用DP如何去做这个问题的例子吗?我理解DP,但我不确定如何将它应用于这个问题,以便它将输出路径......

我真的只想知道如何为比赛做这些比赛,这不是学校分配或任何事情。

编辑:n应该不超过20
分析模式




邮政发布: 2009年5月23日星期六晚上8:30  帖子主题:RE:不确定如何接近...

您有一个2D数组,其中数组中的元素表示最佳可能性,您可以获得一定点(DP [x] [y])。基于较小问题,DP围绕建筑解决方案到更大的问题。而在这个问题中,你知道以前的解决方案是最佳的,因为你不能倒退。如果可以,那么你必须使用图论。

我假设你知道递归吗?然后在这种情况下,您了解基本情况。就像在递归中一样,您必须设置基本情况。因此,应将DP阵列的最左图初始化为网格中的各个收费。

现在为DP:

从网格的左上角开始并扫描,加入通行费。在添加收费时,在网格[x] [y]中记录max(current_sum,dp [x] [y]),其中x和y表示当前位置。做同样的上升和从底部开始。

现在,你从最左边的列中的每个点开始。从那些点,移动ne,e,se,并做我刚刚描述的扫描。除了最后一个之外,对于网格中的每一个列重复此问题。

您的最佳答案将是最后一列,您可以通过它进行简单的搜索来查找答案。
SaltPro15




邮政发布: 2009年5月23日星期六晚上8:57  帖子主题:RE:不确定如何接近...

啊谢谢你! +业力 很高兴

自我注意:奉献一部分生活,以记忆DP ......
分析模式




邮政发布: 2009年5月23日星期六晚上9:32  帖子主题:RE:不确定如何接近...

我忽略了一件事而且正在输出路径。当您通过阵列扫描时,您遇到了小于当前值的DP [x] [y] Calue时,请将先前的最佳路径替换为新的。我建议保留2D数组数组(A.k.a.A. 3D数组)来执行此操作。您也可以使用2D阵列(C ++ / Java)(C ++ / Java),如您所能要更容易的那样更容易,而无需跟踪大小,如果您只使用数组需要执行此小。但是,您的代码将花费稍长才能运行,但它不会是AC和TLE之间的区别。

哦,这个问题与CCC高级问题非常相似,超级水管工。

与算法代码不同,DP不是您记忆的内容。这是一种思考的方式,需要时间才能掌握。这就像冬青,原始粘液或魔法聚会;基本规则很简单,但更先进的想法更难以掌握。
A.J.




邮政发布: 2009年5月23日星期六晚上9:52  帖子主题:RE:不确定如何接近...

@Analysis模式 - 超级水管工略有不同,但是,这个问题是相同类型的DP(即具有相同的复杂性)。

要加入到什么分析模式下,动态编程只是一种解决“更大”问题的方法,通过将它们分成“更小”,更简单的步骤。而且你不应该留下它,因为你肯定会遇到你可能需要改变算法的问题,以便使其工作。因此,保证如何解决一个特定类型的DP问题(或全部记住任何内容)非常不推荐。
SaltPro15




邮政发布: 孙5月24日,2009年7:54 AM  帖子主题:RE:不确定如何接近...

哦,当然,我只是打算记住语法。谢谢你的建议。
Corriep.




邮政发布: Sun 5月24日,2009年10:08 PM  帖子主题:Re:Re:不确定如何接近...

A.J. @ 2009年5月23日星期六10:55写道:
这个编程比赛是什么?有没有办法,我可以参加它吗? (随着比赛季节结束,我有点厌倦了Usaco,Topcoder是我现在唯一能做的事情......好吧,还有其他在线,如Spoj,但我宁愿做实际的比赛)
不!不!不!
aj是不允许的!我打算在这场比赛中进来。
从上一个显示帖子:   
   指数 -> 竞赛
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题

12  [ 23 Posts ]
转到页面 1, 2  下一页
跳到:   


Style:  
搜索: