Este problema se puede resolver fácilmente con DP recursivo (en realidad, encuentro dp recursivo mucho más útil para visualizar la secuencia del programa).
Aquí está mi código C ++. Actualizaré la publicación con una explicación completa en unos días (Mis exámenes están en curso, necesito estudiar para eso).
#include
usando el espacio de nombres estándar;
- ¿Cómo manejan las personas el error de profundidad de recursión máxima excedida sin reescribir el código de forma iterativa? (en la programación dinámica de arriba hacia abajo)
- ¿Cuál es tu recurso favorito para aprender sobre programación competitiva?
- ¿Por qué hay una diferencia de complejidad de tiempo entre los algoritmos de clasificación en Java cuando estoy usando Integer e integer?
- ¿Alguien puede aprender programación, algoritmos y estructuras de datos en tres meses y obtener el bronce en la Olimpiada Británica de Informática?
- Cómo ordenar una matriz de vectores de pares, es decir, vector <par v [N], en C ++
int a [25] [25], dp [25] [25], costo [25] [25], n, mn;
// mn es el mínimo de la diferencia de altura máxima a lo largo de cada ruta posible.
// a [i] [j] representa la altura de los edificios.
// dp [i] [j] representa el mínimo de la diferencia de altura máxima en una ruta que pasa
a través de (i, j).
// costo [i] [j] representa el costo desde el próximo edificio hasta el (n, n) th edificio
siguiendo el camino con la máxima diferencia de altura de mn
int resolver (int x, int y) {
if ((x == n-1 && y == n) || (x == n && y == n-1)) {
dp [x] [y] = abs (a [n] [n] -a [x] [y]);
devuelve dp [x] [y];
}
if (dp [x] [y]! = INT_MAX) {
devuelve dp [x] [y];
}
int p = INT_MAX, q = INT_MAX;
si (x + 1 <= n) {
p = max (abs (a [x + 1] [y] -a [x] [y]), resolver (x + 1, y));
}
si (y + 1 <= n) {
q = max (abs (a [x] [y + 1] -a [x] [y]), resolver (x, y + 1));
}
dp [x] [y] = min (p, q);
devuelve dp [x] [y];
}
int getcost (int x, int y) {
if ((x == n-1 && y == n) || (x == n && y == n-1)) {
devolver abs (a [n] [n] -a [x] [y]);
}
int p, q;
if (x + 1 <= n && y + 1 <= n) {
p = max (abs (a [x + 1] [y] -a [x] [y]), resolver (x + 1, y));
q = max (abs (a [x] [y + 1] -a [x] [y]), resolver (x, y + 1));
if (p <= mn && q <= mn) {
costo [x] [y] = min (abs (a [x + 1] [y] -a [x] [y]) + getcost (x + 1, y),
abs (a [x] [y + 1] -a [x] [y]) + getcost (x, y + 1));
} else if (p <= mn) {
costo [x] [y] = abs (a [x + 1] [y] -a [x] [y]) + getcost (x + 1, y);
}más{
costo [x] [y] = abs (a [x] [y + 1] -a [x] [y]) + getcost (x, y + 1);
}
}
más si (x + 1 <= n) {
costo [x] [y] = abs (a [x + 1] [y] -a [x] [y]) + getcost (x + 1, y);
}
más{
costo [x] [y] = abs (a [x] [y + 1] -a [x] [y]) + getcost (x, y + 1);
}
costo de devolución [x] [y];
}
int main () {
int q;
cin >> q;
mientras que (q -) {
int i, j, k, t;
cin >> n >> t;
para (i = 1; i <= n; i ++) {
para (j = 1; j <= n; j ++) {
cin >> a [i] [j];
dp [i] [j] = INT_MAX;
costo [i] [j] = INT_MAX;
}
}
mn = max (a [1] [1], resolver (1,1));
k = a [1] [1] + getcost (1,1);
si (k <= t) {
cout << "SÍ:" << mn << "" << tk << endl;
}más{
cout << "NO \ n";
}
}
}
Si tiene alguna duda o consulta por favor comente. Seguramente actualizaré la publicación dentro de unos días. Hasta entonces, puede obtener ayuda con este código.
Espero que esto ayude.
