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
#include <cstdio>
#include <algorithm>

typedef unsigned long long UInt64;
typedef int Int32;

Int32 g_totalNumberOfCups;
UInt64 *g_costToCheck;
UInt64 g_minimumCost;
bool *g_isCupDefined;

inline UInt64 costToCheck(Int32 i, Int32 j)
{
    return g_costToCheck[i * g_totalNumberOfCups + j];
}

void readInput()
{
    scanf("%i", &g_totalNumberOfCups);

    g_costToCheck = new UInt64[g_totalNumberOfCups * g_totalNumberOfCups];

    for (Int32 i = 0; i < g_totalNumberOfCups; ++i)
        for (Int32 j = i; j < g_totalNumberOfCups; ++j)
            scanf("%llu", g_costToCheck + i * g_totalNumberOfCups + j);
}

UInt64 minimumCostToDefine(Int32 i)
{
    UInt64 cost = costToCheck(i, i);
    Int32 left = i;
    Int32 right = i;

    for (Int32 j = i - 1; j >= 0 && g_isCupDefined[j]; --j)
        left = j;

    for (Int32 j = i + 1; j < g_totalNumberOfCups && g_isCupDefined[j]; ++j)
        right = j;

    for (Int32 u = left; u <= i; ++u)
        for (Int32 v = i; v <= right; ++v)
            if (costToCheck(u, v) < cost)
                cost = costToCheck(u, v);

    return cost;
}

void walk(UInt64 currentCost, Int32 currentNumberOfDefinedCups)
{
    if (currentNumberOfDefinedCups == g_totalNumberOfCups)
    {
        if (currentCost < g_minimumCost)
            g_minimumCost = currentCost;

        return;
    }

    for (Int32 i = 0; i < g_totalNumberOfCups; ++i)
    {
        if (g_isCupDefined[i])
            continue;

        UInt64 newCost = currentCost + minimumCostToDefine(i);

        if (newCost < g_minimumCost)
        {
            g_isCupDefined[i] = true;
            walk(newCost, currentNumberOfDefinedCups + 1);
            g_isCupDefined[i] = false;
        }
    }
}

UInt64 minimumCostBound()
{
    UInt64 bound = 0;

    for (Int32 i = 0; i < g_totalNumberOfCups; ++i)
        bound += costToCheck(i, i);

    return bound;
}

UInt64 solve()
{
    g_isCupDefined = new bool [g_totalNumberOfCups];

    for (Int32 i = 0; i < g_totalNumberOfCups; ++i)
        g_isCupDefined[i] = false;

    g_minimumCost = minimumCostBound();

    walk(0, 0);

    return g_minimumCost;
}

int main()
{
    readInput();
    printf("%llu\n", solve());
    return 0;
}