3

私が立ち往生している問題は、人が整数を含む2次元配列の左上から右下の位置に移動し、下または右に移動して最大のスコアを獲得する必要があることです。ただし、位置 A[i][j] が 0 未満の場合、その人はその位置を通り過ぎることができず、この負の値に等しい量が、そのような位置の近くを訪れるたびにスコアから差し引かれます。 . これは標準的な DP 問題であり、T[i][j] が 0,0 から位置 i,j までの最大スコアを表す配列 T[][] を作成できることを知っています。ただし、負の整数でマークされたセルを人が通り過ぎてはならないという条件を適切に実装することはできません。たとえば、rows=2;column=3; の場合です。と

A= | 0  -4   8 |
   | 1   1   0 |

次に、答えを-6にしたい、つまり行列Tは

 T=| 0  -4   X |
   | -3 -6  -6 |
  1. 開始位置と終了位置で、その人は自分のスコアから「奪われた」わけではありません。
  2. X は、対応する位置に男性が到達できないことを示します。上記の場合、男性は A[0][1] を渡って A[0][2] に行くことはできません。
  3. T[row-1][column-1] は質問の答えです。つまり、A[0][0] から A[row-1][column-1] までの人が取得できる最大スコアです。
4

2 に答える 2

1

アイデアは、最大値として選択されることのない負の無限大の結果を持つ負のセルに移動できないことをエミュレートしています。擬似コード:

int negativePart(int i, int j)
{
    if (i < 0 || j < 0)
        return 0;
    return A[i, j] < 0 ? A[i, j] : 0;
}

int neighborInfluence(int i, int j)
{
    if (int == Height -1 && j == Width - 1)
        return 0;
    return negativePart(i-1, j-1) + negativePart(i-1,j)+// so on, do not think about negative indexes because it was already processed in negativePart method
}

int scoreOf(int i, int j)
{
    return A[i,j] < 0 ? <NegativeInfinity> : A[i,j] + neighborInfluence(i,j);
}

//.......

T[0,0] = A[0,0];
for (int i = 1; i < heigth; ++i)
{
    T[i, j] = T[i - 1, 0] + scoreOf(i, 0);
}

for (int i = 1; i < width; ++i)
{
    T[0, i] = T[0, i - 1] + scoreOf(0, i);
}

for (int i = 1; i < heigth; ++i)
{
    for (int j = 1; j < width; ++j)
    {
        T[i, j] = max(T[i - 1, j], T[i, j - 1]) + scoreOf(i, j);
    }
}
于 2012-08-23T19:30:31.743 に答える
1

dwrdの回答で示唆されているのと同じ考え方に従っていたので、Python で実装してみました。最初は考えていなかった考慮すべき点がいくつかありますが、最終的には機能するようになったと思います.

これがコードです。確かにいくらか磨きをかける必要がありますが、それは始まりです:

def get_score(M, i, j):
    "Get the final score for position [i, j.]"
    score = 0

    if M[i][j] < 0:
        score = -float('inf')
    else:
        score = M[i][j]
        score = score + penalty(M, i - 1, j - 1)
        score = score + penalty(M, i - 1, j + 1)
        score = score + penalty(M, i + 1, j - 1)
        score = score + penalty(M, i + 1, j + 1)
        score = score + penalty(M, i - 1, j)
        score = score + penalty(M, i, j - 1)
        score = score + penalty(M, i + 1, j)
        score = score + penalty(M, i, j + 1)

    return  score

def penalty(M, i, j):
    "Calculate the penalty for position [i, j] if any."
    if i >= 0 and i < len(M) and j >= 0 and j < len(M[0]):
        return (0 if M[i][j] > 0 else M[i][j])

    return 0

def calc_scores(M):
    "Calculate the scores matrix T."
    w = len(M[0])
    h = len(M)
    T = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            T[i][j] = get_score(M, i, j)

    T[0][0] = 0
    T[h - 1][w - 1] = 0

    return T

def calc_max_score(A, T):
    "Calculate max score."
    w = len(A[0])
    h = len(A)
    S = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            S[i][j] = max(S[i - 1][j], S[i][j - 1]) + T[i - 1][j - 1]

            # These are for the cases where the road-block
            # is in the frontier
            if A[i - 1][j - 2] < 0 and i == 1:
                S[i][j] = -float('inf')

            if A[i - 2][j - 1] < 0 and j == 1:
                S[i][j] = -float('inf')
    return S

def print_matrix(M):
    for r in M:
        print r

A = [[0, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

A = [[0, 1, 1], [4, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

次の出力が得られます。

----------
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -inf, -inf]
[0, -3, -6, -6]
----------

----------
[0, -3, -3]
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -3, -3]
[0, 0, -inf, 1]
[0, -3, -6, 1]
----------
于 2012-08-23T20:44:56.487 に答える