333 条题解
-
0
hunter LV 3 @ 2007-07-20 16:57:28
BT! 还有没有天理,这种数据......
无语...... -
0
Fallen-Angel LV 3 @ 2007-07-19 00:02:19
f[i]=min(f+p[i]);
{ p[i]=0 or 1
j:=s to t do }
我用的路径压缩是:l=stone[i]-stone;
if(l mod t=0)then temp=l mod t+t
else temp=t*2;
if temp>l then temp:=l; -
0
LV 0 @ 2007-07-16 21:10:03
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：20 有效耗时：0ms
无语ing
ps：楼下的用的是小号吧！
楼下的楼下就是你的小号吧！
(*^__^*) 嘻嘻…… -
0
显然的算法，肯定是使用 Dynamic Programming。
同样的问题，一般的动态规划虽然复杂度虽然不高，只是这个数据范围实在是变态。O(l*t)的复杂度用数值表示就是上亿次。一点都不高。
在这个时候，师兄对我说：Dynamic Programming 的复杂度最低是输入复杂度。所以就想到了路径压缩。
路径压缩从理论上是可行的。从某一个点开始，下一个点如果离它的距离在某一个值之外，就可以到达这个值之外的任意一个点。关键在于怎样找到这个长度。
首先，这个长度随s、t的改变而改变。就可以推想到这个长度和s、t有关。设这个长度为m。
我首先想到的是：m=s*t。这个的结果很不好看。
然后我看了前人的解题报告。上面说值是m=s*t+t。因此我又算了一遍。这个解出来能过8个点。
在接着我用系统可以接受的数据范围时使用最初的最保险的 Dynamic Programming，又过了一个点。
最后，压缩的条件变成了： if m>t then m:=t+(m-1) mod t+1
这个条件也是试了C语言的那个伙伴，就是楼下的那个大哥的见解。结果真的过了全部的点。但还是没有考虑清楚为什么可以这样压缩。倒是希望大家帮我解决。 -
0
ZhouYuChen LV 5 @ 2007-06-18 10:19:05
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法我~~~~~~~
-
0
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 04：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 09：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0ms
我彻底无奈了 -
0
chenqizhou8 LV 3 @ 2007-04-22 10:33:36
谁能告诉俺怎么压缩坐标啊?!!!
-
0
little zaza LV 3 @ 2007-04-08 22:17:16
{看起来是个简单的动态规划，但是数据十分大，所以直接动态规划时不行的。注意到石头非常稀疏，所以在距离大于一定范围的点总是可以到达的，经试验这个值取90即可。所以对于距离大于90的两块石头把他们的距离设为90，然后用原来的规划方程来动态规划。不过在S=T的情况下要注意一下，不能用这种压缩距离的方法做，而要直接看能否走到。}
.... 为什么要设90呢，直接设成t的只就行了啊。
因为如果间距大于t，只能是从空白处跳来，这样的计算是无意义的。。
hunter
LV 3
@ 2007-07-20 16:57:28
