DouKaku?beta

Comment detail

情報オリンピック2007年度国内本選問題4 (Nested Flatten) 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cassert>

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define REPE(i, b, e) for (size_t i = b; i <= e; ++i)

void fill(std::vector<long>& v, long value)
{
    std::fill(v.begin(), v.end(), value);
}

int main()
{
    const size_t max_x = 1000;

    std::string s;

    std::getline(std::cin, s);

    size_t n, m;

    std::istringstream(s) >> n >> m;

    assert(2 <= n && n <= 150);

    assert(m <= (n + 1) / 2);

    std::vector<std::vector<long> > slip(n + 3, std::vector<long>(max_x, -1)); // -1 means there is no stone

    fill(slip[0], 0); // start shore (0 is dummy value)

    fill(slip[n + 1], 0); // goal shore (0 is dummy value)

    fill(slip[n + 2], 0); // goal shore (0 is dummy value)

    REPE(y, 1, n)
    {
        std::getline(std::cin, s);

        std::istringstream sin(s);

        size_t k;

        sin >> k;

        assert(k <= 10);

        for (; k; --k)
        {
            size_t x;

            long d;

            sin >> x >> d;

            assert(1 <= x && x <= max_x);

            assert(1 <= d && d <= 1000);

            --x; // now starts with 0 not 1

            slip[y][x] = d;
        }
    }

    std::vector<std::vector<std::vector<long> > > dp(n + 3,
        std::vector<std::vector<long> >(max_x,
            std::vector<long>(m + 1, std::numeric_limits<long>::max())));

    dp.front().swap(
        std::vector<std::vector<long> >(max_x,
            std::vector<long>(m + 1, 0)));

    REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
    {
        REPE(y2, y1 + 1, y1 + 2) REP(x2, 0, max_x) if (slip[y2][x2] >= 0) // destinition
        {
            const size_t now_jumped = y2 - y1 - 1;

            assert(now_jumped == 0 || now_jumped == 1);

            for (size_t old_jumped = 0; old_jumped + now_jumped <= m; ++old_jumped)
            {
                if (dp[y1][x1][old_jumped] != std::numeric_limits<long>::max())
                {
                    long& src = dp[y1][x1][old_jumped];

                    long& dst = dp[y2][x2][old_jumped + now_jumped];

                    dst = std::min(dst, src + (slip[y1][x1] + slip[y2][x2]) * long(x2 > x1 ? x2 - x1 : x1 - x2));
                }
            }
        }
    }

    long result = std::numeric_limits<long>::max();

    REPE(y, n + 1, n + 2) REP(x, 0, max_x) REPE(jumped, 0, m) // goal shore
    {
        result = std::min(result, dp[y][x][jumped]);
    }

    std::cout << result << std::endl;
}

g++でコンパイルが通らなかったので、修正。（理由は不明）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
--- 4.cpp.old    Thu May 22 16:17:00 2008
+++ 4.cpp.new    Thu May 22 16:16:47 2008
@@ -72,9 +72,7 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp.front().swap(
-        std::vector<std::vector<long> >(max_x,
-            std::vector<long>(m + 1, 0)));
+    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

cppリファレンスによるとswap は
void swap( vector &from );となっているので
一時変数の参照型がまずいのではないでしょうか？

gfilt にかけても↓のような感じに出てくるので
たぶんそこを直せば何とかなるのでは？

gfilt -Wall 6316.cpp
BD Software STL Message Decryptor v3.10 for gcc 2/3/4
6316.cpp: In function `int main()':
6316.cpp:76: error: No match for
   `vector<vector<long int> >::swap(vector<vector<long int>>)'
stl_vector.h:688: candidates are: void vector<
        vector<long int> >::swap(vector<vector<long int> > &)

see: C/C++ リファレンス

情報ありがとうございます。こっちならうまくいきました。

see: 今のところswapに一時変数は渡せない 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
--- 4.cpp.new    Fri May 23 15:31:57 2008
+++ 4.cpp.new2    Fri May 23 15:32:13 2008
@@ -72,7 +72,8 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
+    std::vector<std::vector<long> >(max_x,
+        std::vector<long>(m + 1, 0)).swap(dp.front());
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

いっそ、こっちの方が読みやすいかも

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
--- 4.cpp.new    Fri May 23 15:31:57 2008
+++ 4.cpp    Fri May 23 15:41:55 2008
@@ -9,9 +9,9 @@
 #define REP(i, b, e) for (size_t i = b; i < e; ++i)
 #define REPE(i, b, e) for (size_t i = b; i <= e; ++i)
 
-void fill(std::vector<long>& v, long value)
+void zero_fill(std::vector<long>& v)
 {
-    std::fill(v.begin(), v.end(), value);
+    std::fill(v.begin(), v.end(), 0);
 }
 
 int main()
@@ -32,11 +32,11 @@
 
     std::vector<std::vector<long> > slip(n + 3, std::vector<long>(max_x, -1)); // -1 means there is no stone
 
-    fill(slip[0], 0); // start shore (0 is dummy value)
+    zero_fill(slip[0]); // start shore (0 is dummy value)
 
-    fill(slip[n + 1], 0); // goal shore (0 is dummy value)
+    zero_fill(slip[n + 1]); // goal shore (0 is dummy value)
 
-    fill(slip[n + 2], 0); // goal shore (0 is dummy value)
+    zero_fill(slip[n + 2]); // goal shore (0 is dummy value)
 
     REPE(y, 1, n)
     {
@@ -72,7 +72,7 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
+    std::for_each(dp.front().begin(), dp.front().end(), zero_fill);
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]