Skip to Content
CTRL K

Array Description

Editorial (C++) 

Explicación

Definimos dp[i][j]\text{dp}[i][j] como la cantidad de formas de llenar los primeros ii elementos del arreglo, de modo que ai=ja_i = j.

Caso base: si x1=0x_1 = 0, entonces el primer elemento es desconocido y puede ser cualquier cosa de 11 a mm, así que dp[1][j]=1\text{dp}[1][j] = 1 para todo jj. En caso contrario, el primer elemento está fijo, así que dp[1][x1]=1\text{dp}[1][x_1] = 1 y todos los demás dp[1][j]=0\text{dp}[1][j] = 0.

Para i>1i > 1, como los elementos adyacentes difieren en a lo sumo 11, ai=ja_i = j es posible solo si ai−1a_{i-1} es j−1j-1, jj o j+1j+1:

dp[i][j]=dp[i−1][j−1]+dp[i−1][j]+dp[i−1][j+1] \text{dp}[i][j] = \text{dp}[i-1][j-1] + \text{dp}[i-1][j] + \text{dp}[i-1][j+1]

Podemos usar la misma idea vista en Grid Paths , donde una celda trampa fuerza dp[x][y]=0dp[x][y] = 0 porque ningún camino puede terminar ahí. Luego, ponemos dp[i][j]=0\text{dp}[i][j] = 0 cuando el índice ii está fijo a un valor distinto de jj, porque ningún arreglo válido puede tener ai=ja_i = j en ese caso.

Calculamos la respuesta final sumando dp[n][j]\text{dp}[n][j] sobre todos los jj de 11 a mm.

Implementación

Complejidad temporal: O(NM)\mathcal{O}(NM)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int MOD = 1e9 + 7;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	vector<int> values(n + 1);
	for (int i = 1; i <= n; i++) { cin >> values[i]; }
 
	// dp[position][value] es la cantidad de formas de llenar los primeros "position" elementos
	// del arreglo de modo que el elemento en "position" sea igual a value
	vector<vector<ll>> dp(n + 1, vector<ll>(m + 1));
 
	// caso base: el primer elemento está fijo o es libre de ser 1..m
	if (values[1] == 0) {
		for (int j = 1; j <= m; j++) { dp[1][j] = 1; }
	} else {
		dp[1][values[1]] = 1;
	}
 
	for (int position = 2; position <= n; position++) {
		int fixed_value = values[position];
		for (int val = 1; val <= m; val++) {
			// si esta posición está fija y no coincide con j, es inalcanzable
			if (fixed_value != 0 && fixed_value != val) { continue; }
 
			// si no, j se puede alcanzar desde j-1, j o j+1 en el índice anterior
			dp[position][val] = dp[position - 1][val];
			if (val - 1 >= 1) { dp[position][val] += dp[position - 1][val - 1]; }
			if (val + 1 <= m) { dp[position][val] += dp[position - 1][val + 1]; }
			dp[position][val] %= MOD;
		}
	}
 
	ll ans = 0;
	for (int j = 1; j <= m; j++) { ans = (ans + dp[n][j]) % MOD; }
 
	cout << ans << '\n';
}
 
import java.io.*;
import java.util.*;
 
public class ArrayDesc {
	public static final int MOD = (int)1e9 + 7;
	public static void main(String args[]) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		// dp[i][j] es la cantidad de formas de llenar los primeros i+1 elementos
		// del arreglo de modo que el i-ésimo elemento sea igual a j
		int[][] dp = new int[N][M + 1];
 
		// caso base: el primer elemento está fijo o es libre de ser 1..M
		StringTokenizer arr = new StringTokenizer(r.readLine());
		int first = Integer.parseInt(arr.nextToken());
 
		// si el primer elemento es libre, puede ser cualquier valor de 1..M
		if (first == 0) {
			Arrays.fill(dp[0], 1);
		} else {
			// si no, el primer elemento está fijo
			dp[0][first] = 1;
		}
 
		for (int i = 1; i < N; i++) {
			int A = Integer.parseInt(arr.nextToken());
			// si esta posición es libre, probar todos los valores 1..M
			if (A == 0) {
				for (int j = 1; j <= M; j++) {
					int[] neighborVals = new int[] {j - 1, j, j + 1};
					for (int k : neighborVals) {
						// j se puede alcanzar desde j-1, j o j+1 en el índice anterior
						if (1 <= k && k <= M) {
							dp[i][j] += dp[i - 1][k];
							dp[i][j] %= MOD;
						}
					}
				}
			} else {
				// si esta posición está fija a A,
				// solo se puede alcanzar desde A-1, A o A+1
				int[] neighborVals = new int[] {A - 1, A, A + 1};
				for (int k : neighborVals) {
					if (1 <= k && k <= M) {
						dp[i][A] += dp[i - 1][k];
						dp[i][A] %= MOD;
					}
				}
			}
		}
 
		// sumar sobre todos los valores posibles del último elemento
		int ans = 0;
		for (int j = 1; j <= M; j++) {
			ans += dp[N - 1][j];
			ans %= MOD;
		}
 
		System.out.println(ans);
	}
}
Fundamentos