ACM题(#2634 Collecting Stones)

lugionline

有个很强的条件不知道大家有没有注意到，加上这个条件后不展开的情况下 基本上5秒出结果

        -- 从i列转到i+1/i-1列时要满足的约束
        -- 1-4列下界，(当前列之前总和 - 当前采集总和) <= (总数 - @m)
        -- 1-4列上界，(当前采集总和 < @m - 后面每列上最小值总和)
        -- 5-8列下界，(当前列之前总和 - 当前采集总和) <= (总数 - @m)
        -- 5-8列上界，(当前采集总和 < @m - 前面每列上最小值总和)

〇〇

基本上5秒出结果是指1个问题还是20个问题？

lugionline

一个问题，呵呵，加上前面那个条件时就是数字大时会快，我写的比较烂，就当抛块砖吧

declare @m int = 1500;

with
d(n) as (select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7),
cost(i, j, v) as (select d1.n, d2.n, d1.n * 8 + d2.n + 1 from d d1, d d2),
total(n) as (select sum(v) from cost),
m(j, v) as (select j, min(v) from cost group by j), -- 每列上的最小值
bound(j, low, high) as
(
        -- 从i列转到i+1/i-1列时要满足的约束
        -- 1-4列下界，(当前列之前总和 - 当前采集总和) <= (总数 - @m)
        -- 1-4列上界，(当前采集总和 < @m - 后面每列上最小值总和)
        -- 5-8列下界，(当前列之前总和 - 当前采集总和) <= (总数 - @m)
        -- 5-8列上界，(当前采集总和 < @m - 前面每列上最小值总和)
        select d.n,
                (select sum(v) from cost where j <= d.n) - (total.n - @m),
                @m - (select sum(v) from m where m.j > d.n)
        from d, total where d.n < 4
        union
        select d.n,
                (select sum(v) from cost where j >= d.n) - (total.n - @m),
                @m - (select sum(v) from m where m.j < d.n)
        from d, total where d.n >= 4
),
direction(j, i) as
(
        select 1, 1 union
        select 1, 0 union
        select 1, -1 union
        select 0, 1 union
        select 0, -1),
path14(i, j, v, s) as
(
        select 0, 0, v,
                cast('x' as char(64)) s from cost where i = 0 and j = 0
        union all
        select p.i + d.i, p.j + d.j, p.v + c.v,
                cast(stuff(p.s, 8 * (p.i + d.i) + p.j + d.j + 1, 1, 'x') as char(64)) s
        from path14 p, direction d, cost c, bound
        where p.i + d.i >= 0 and p.i + d.i < 8 -- 在网格内
                and p.j + d.j >= 0 and p.j + d.j < 4
                and substring(p.s, 8 * (p.i + d.i) + p.j + d.j + 1, 1) <> 'x' -- 没访问过
                and p.i + d.i = c.i and p.j + d.j = c.j -- 取得费用
                and p.v + c.v <= @m
                and p.j = bound.j -- 上下确界
                and (d.j = 0 or (p.v >= bound.low and p.v <= bound.high))
),
path85(i, j, v, s) as
(
        select 7, 7, v,
                cast(stuff(space(64), 8 * 7 + 7 + 1, 1, 'x') as char(64)) s
        from cost where i = 7 and j = 7
        union all
        select p.i - d.i ni, p.j - d.j nj, p.v + c.v nv,
                cast(stuff(p.s, 8 * (p.i - d.i) + p.j - d.j + 1, 1, 'x') as char(64)) ns
        from path85 p, direction d, cost c, bound
        where p.i - d.i >= 0 and p.i - d.i < 8 -- 在网格内
                and p.j - d.j >= 0 and p.j - d.j >= 4
                and substring(p.s, 8 * (p.i - d.i) + p.j - d.j + 1, 1) <> 'x' -- 没访问过
                and p.i - d.i = c.i and p.j - d.j = c.j -- 取得费用
                and p.v + c.v <= @m
                and p.j = bound.j -- 上下确界
                and (d.j = 0 or (p.v >= bound.low and p.v <= bound.high))
),
pa(i, v) as
(
        select i,v from path14 p, bound b
        where p.j=3 and b.j = 3 and p.v >= b.low and p.v <= b.high
),
pb(i, v) as
(
        select i,v from path85 p, bound b
        where p.j=4 and b.j = 4 and p.v >= b.low and p.v <= b.high
)
select top 1 * from pa a , pb b
where        (a.i = b.i or a.i = b.i + 1 or a.i = b.i - 1)
        and a.v + b.v = @m -- 取值

〇〇

oracle 的stop key执行计划还是很厉害的

影之哀伤

现在是不是集中在提升效率上了啊?

PL/SQL上怎么判断哪个效率好啊？

a:=a+1
if a=1
比如上面两个操作 哪个执行起来会更快啊

〇〇

用下面的数据

SQL> @c:\downloads\testcte3

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,33,41,49,57,58,50,42,34,26,18,10,2,3,11,19,27,35,43,51,59,60,52,44,36,28,20,12,4*5,13,21,29,37,45,53,61,62,54,46,38,30,22,14,6,7,15,23,31,3
9,47,55,63,56,64,


已用时间:  00: 00: 03.68

WITH d AS (                                    
  SELECT to_char(ROWNUM,'fm09') id              
        ,CEIL(ROWNUM/8) r                       
        ,MOD(ROWNUM-1,8)+1 c                    
        ,trunc(dbms_random.value(1,2000001)) val
    FROM DUAL                                   
   CONNECT BY ROWNUM<=64                        
  )select * from d;                             


exec :m:=57651170
WITH d AS (                          
select 01 id,1 r,1 c,1893148 val from dual union
select 02,1,2,1890548 from dual union
select 03,1,3,1798382 from dual union
select 04,1,4, 823916 from dual union
select 05,1,5,1437670 from dual union
select 06,1,6, 956535 from dual union
select 07,1,7, 202623 from dual union
select 08,1,8,1262316 from dual union
select 09,2,1,1974188 from dual union
select 10,2,2,1307861 from dual union
select 11,2,3, 727655 from dual union
select 12,2,4, 298448 from dual union
select 13,2,5, 458997 from dual union
select 14,2,6,1094767 from dual union
select 15,2,7,1314543 from dual union
select 16,2,8, 901497 from dual union
select 17,3,1, 920073 from dual union
select 18,3,2, 402348 from dual union
select 19,3,3, 699867 from dual union
select 20,3,4, 148556 from dual union
select 21,3,5,1983591 from dual union
select 22,3,6,  33022 from dual union
select 23,3,7, 489689 from dual union
select 24,3,8,1248730 from dual union
select 25,4,1,1843016 from dual union
select 26,4,2, 554026 from dual union
select 27,4,3, 865738 from dual union
select 28,4,4,1859072 from dual union
select 29,4,5, 230106 from dual union
select 30,4,6, 929438 from dual union
select 31,4,7, 696728 from dual union
select 32,4,8, 821498 from dual union
select 33,5,1,1565073 from dual union
select 34,5,2, 371760 from dual union
select 35,5,3,1402380 from dual union
select 36,5,4, 309730 from dual union
select 37,5,5, 251062 from dual union
select 38,5,6, 805244 from dual union
select 39,5,7, 179326 from dual union
select 40,5,8, 636030 from dual union
select 41,6,1,1011401 from dual union
select 42,6,2,  29878 from dual union
select 43,6,3,1207144 from dual union
select 44,6,4,1950166 from dual union
select 45,6,5,1746687 from dual union
select 46,6,6,1770509 from dual union
select 47,6,7,1921779 from dual union
select 48,6,8,1876739 from dual union
select 49,7,1,1936806 from dual union
select 50,7,2, 136189 from dual union
select 51,7,3,1139278 from dual union
select 52,7,4,1641397 from dual union
select 53,7,5,1377942 from dual union
select 54,7,6, 303408 from dual union
select 55,7,7, 815606 from dual union
select 56,7,8, 432729 from dual union
select 57,8,1, 191754 from dual union
select 58,8,2, 670916 from dual union
select 59,8,3,1441426 from dual union
select 60,8,4,1589992 from dual union
select 61,8,5,1119946 from dual union
select 62,8,6, 716922 from dual union
select 63,8,7,1211227 from dual union
select 64,8,8, 568942 from dual)

lugionline

彼此彼此，把cost数据放到一个单独临时表中后的结果

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
i           v           i           v
----------- ----------- ----------- -----------
0           34602132    0           23049038

(1 row(s) affected)


SQL Server Execution Times:
   CPU time = 3687 ms,  elapsed time = 3719 ms.

rollingpig

N
-
Y

Elapsed: 00:00:00.53

530ms.

〇〇

原帖由 rollingpig 于 2011-4-14 16:44 发表
N
-
Y

Elapsed: 00:00:00.53

530ms.

20题5秒快有希望了

rollingpig

我尝试改为java写的，算石头时加上下限限制。
M=900-1200时竟然还是需要半秒。
但是你后来提供的数据，用了上下线限制后，24ms就成了。

countColumn:1ms
一行/两行/三行/四行/最终
8 576 5040 13680 673
joinColumn14:9
8行/7行/6行/5行/最终
8 576 4464 23256 772
joinColumn85:累计21ms
YES, St1： 34602132， St2: 23049038
finalJoin:累计24ms