Задача по динамическому программированию: «Карьерный путь в Tune-IT»

Условия задачи

В компании Tune-IT программист строит карьеру, зарабатывая славу, деньги и влияние в зависимости от выбранного пути. Слава, деньги и влияние дают A, B и C очков репутации и D, E, F очков выгорания соответственно. Программист хоть и мечтает получить как можно больше репутации, но если он выгорит, то больше не сможет писать чистый, легко-масштабируемый код, способный менять мир к лучшему. У каждого программиста есть свой предельный уровень выгорания H, после которого он начинает думать об увольнении. Также дана карта возможностей M x N, показывающая, где можно получить славу, деньги и влияние,  а где – ничего. На карте возможности отмечены буквами “С”, “Д”, “В” и “Н“. 

Задача

Необходимо найти такой карьерный путь (на карте возможностей), который обеспечит программисту в Tune-IT максимальную репутацию, и при этом не даст ему выгореть. Двигаться по карте возможностей можно на клетку вверх, вниз, вправо и влево начиная с верхней левой клетки. В качестве результата необходимо вывести максимальное число очков репутации. В случае, когда любой выбор карьерного пути приводит к выгоранию, выведите -1.

Входные данные

• H – предельный уровень выгорания

• M, N – размер матрицы возможностей

• A, B и C – очки репутации, которые дает слава, деньги и влияние соответственно

• D, E и F – очки выгорания, которые дает слава, деньги и влияние соответственно

• availability – матрица возможностей M x N, заполненная буквами “С”, “Д”, “В” и “Н“

Выходные данные

• Максимальное число очков репутации или -1, если любой выбор карьерного пути приводит к выгоранию

Примеры

​​​​​​Ввод:

1

1 1

1 2 3

1 2 3

Н

Вывод:

0

Если без воды и кратко – нужно найти путь по сетке M×N с движениями в 4 направления, который максимизирует суммарную репутацию при ограничении на суммарный уровень выгорания (не превышать H). Каждая клетка даёт либо один из трёх типов вознаграждений (репутация + выгорание) либо ничего. Если все пути приводят к выгоранию (> H), ответ – -1.

Это задача оптимизации с ограничением ресурса (burnout) на графе-решётке. Подход динамического программирования на клетках с учётом расходуемого ресурса (выгорания) даёт решение за O(M·N·(H+1)). Однако можно сделать O(M·N) по состояниям, если воспользоваться тем, что значения вознаграждений и издержек фиксированы и не зависят от скорости: здесь разумное и простое решение – BFS/динамика в пространстве (i, j, b), где b – текущее выгорание (0..H). Это динамика на взвешенном графе с неотрицательными прибавками: для каждого состояния храним максимальную репутацию, достижимую при данном выгорании. Переходы увеличивают выгорание на D/E/F (или 0) и репутацию на A/B/C (или 0) при заходе в соседнюю клетку.

Ключевые шаги решения

1. Кодируем для каждой буквы репутацию и выгорание: С→(A,D), Д→(B,E), В→(C,F), Н→(0,0).

2. Состояние – (i,j,b) где b ∈ [0..H] – текущая клетка и накопленное выгорание. Храним best[i][j][b] = максимальная репутация при достижении этого состояния.

3. Инициализация: стартовое состояние – верхняя левая клетка (0,0). Если её burn > H, ответ −1 (нельзя даже стартовать). Иначе стартовое best[0][0][burn0] = reward0. При старте мы посещаем (0,0) и применяем её эффекты.

4. По очереди (BFS/deque) релаксируем переходы в 4 направления: для соседа nb = b + burn(neigh); если nb ≤ H, обновляем best[ni][nj][nb] = max(...).

5. Ответ – максимум best[i][j][b] по всем i,j,b. Если ни одно состояние недостижимо – выводим - 1.

Код алгоритма на kotlin:

​​​​​​​import java.io.BufferedReader

import java.io.InputStreamReader

import java.util.ArrayDeque

import kotlin.math.max

data class S(val i:Int, val j:Int, val b:Int)
 

fun main(){

    val br = BufferedReader(InputStreamReader(System.`in`))

    val toks = ArrayDeque<String>()

    fun next(): String {

        while(toks.isEmpty()){

            val line = br.readLine() ?: return ""

            line.trim().split(Regex("\\s+")).filter{it.isNotEmpty()}.forEach{toks.addLast(it)}

        }

        return toks.removeFirst()

    }
 

    val H = next().toInt()

    val M = next().toInt(); val N = next().toInt()

    val A = next().toInt(); val B = next().toInt(); val C = next().toInt()

    val D = next().toInt(); val E = next().toInt(); val F = next().toInt()
 

    val g = Array(M){ CharArray(N) }

    for(i in 0 until M){

        var s = next()

        if(s.length < N){

            val sb = StringBuilder(s)

            while(sb.length < N) sb.append(next())

            s = sb.toString()

        }

        for(j in 0 until N) g[i][j] = s[j]

    }
 

    fun reward(c:Char) = when(c){ 'С','C'->A; 'Д'->B; 'В','V'->C; else->0 }

    fun burn(c:Char) = when(c){ 'С','C'->D; 'Д'->E; 'В','V'->F; else->0 }
 

    val NEG = Int.MIN_VALUE/4

    val best = Array(M){ Array(N){ IntArray(H+1){ NEG } } }

    val q = ArrayDeque<S>()
 

    val sb0 = burn(g[0][0])

    if(sb0 > H){ println(-1); return }

    best[0][0][sb0] = reward(g[0][0])

    q.add(S(0,0,sb0))
 

    val di = intArrayOf(-1,1,0,0); val dj = intArrayOf(0,0,-1,1)

    while(q.isNotEmpty()){

        val cur = q.removeFirst()

        val curV = best[cur.i][cur.j][cur.b]

        for(d in 0..3){

            val ni = cur.i + di[d]; val nj = cur.j + dj[d]

            if(ni !in 0 until M || nj !in 0 until N) continue

            val nb = cur.b + burn(g[ni][nj])

            if(nb > H) continue

            val nv = curV + reward(g[ni][nj])

            if(nv > best[ni][nj][nb]){

                best[ni][nj][nb] = nv

                q.add(S(ni,nj,nb))

            }

        }

    }
 

    var ans = NEG

    for(i in 0 until M) for(j in 0 until N) for(b in 0..H) ans = max(ans, best[i][j][b])

    println(if(ans <= NEG/2) -1 else ans)

}