Drought

Análisis oficial (C++) 

Análisis alternativo (C++) 

Explicación

Consideremos un caso en el que tenemos solo dos vacas.

En cualquier caso en que los dos valores de hambre son iguales, ¡siempre es posible reducirlos ambos a cero! (disminuyendo elementos adyacentes).

Sin embargo, con tres vacas:

No podemos aplicar la misma transformación. De hecho, para cualquier número impar de vacas, es imposible garantizar que podamos decrementar todos los elementos a cero aunque todos los elementos sean iguales.

Esto nos motiva a partir el problema en dos casos: $N$ par y $N$ impar.

Si $N$ es par, entonces podemos contar el número de tuplas tales que todos los elementos están en cero porque podemos garantizar que esta tupla puede alcanzar todos los estados iguales y viceversa.

Sin embargo, si $N$ es impar, no podemos hacer la misma suposición: ¡podrían ser iguales en cualquier valor! Así, tenemos que contar el número de tuplas para todos los niveles de hambre posibles $x$. Para contemplar esto, nótese que al desplazar el techo de los datos en $x$, podemos hallar la respuesta para poner todas las vacas en $x$ con el mismo proceso de antes.

¿Qué información hay que llevar después de procesar las primeras $i$ vacas?

Aunque parezca que el índice es todo lo que necesitamos, como solo podemos disminuir la vaca más a la derecha con la de su izquierda, también hay que llevar la cuenta del valor de hambre de la vaca actual para no hacer imposible llevar a cero a la vaca más a la derecha.

Más formalmente, si $\texttt{dp}[i][j] =$ el número de tuplas que se pueden formar si los primeros $i - 1$ elementos están en cero y el $i$-ésimo elemento tiene valor de hambre $j$, entonces este estado afecta a todos los estados $\texttt{dp}[i + 1][k - h_i]$ tales que $h_i \leq k \leq h_{i + 1}$.

¡Calculemos la complejidad temporal!

Tendremos $N \cdot \max H$ estados, y cada transición puede tomar hasta $\max H$ operaciones, así que nuestra complejidad temporal sería $\mathcal{O}(N(\max H)^2)$. Lamentablemente, en los casos impares, tendremos que probar todos los $x < \min H$ posibles, lo que nos da una complejidad temporal resultante de $\mathcal{O}(N(\max H)^3)$ (ya que todos los elementos pueden ser iguales).

Por suerte, como nuestra transición actualiza un rango contiguo de estados ($[0, h_i]$), podemos procesar la transición en $\mathcal{O}(1)$ con un arreglo de diferencias. Por ejemplo, si estamos en $\texttt{dp}[i][j]$, nuestro algoritmo sumaría manualmente $\texttt{dp}[i][j]$ a $\texttt{dp}[i + 1][k]$ donde $k$ está en el rango $[0, h_i]$. En su lugar, sumaremos $\texttt{dp}[i][j]$ a $\texttt{diff}[0]$ y nos acordaremos de restarlo en $\texttt{diff}[h_i]$.

¡Esto acelera nuestro algoritmo a $\mathcal{O}(N(\max H)^2)$!

Implementación

Complejidad temporal: $\mathcal{O}(N(\max H)^2)$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MOD = 1e9 + 7;
const int MX_HUNGER = 1000;
 
int n;
 
ll ways_offset(int shift, vector<int> &h, vector<ll> &dp, vector<ll> &diff) {
	// inicialmente hay una forma de poner los primeros i elementos en cero
	for (int i = 0; i <= MX_HUNGER; i++) { dp[i] = 1; }
 
	// formas considerando que todos los números antes de i son cero e i está puesto en j
	for (int i = 1; i < n; i++) {
		int j = 0;
		while (j <= (h[i - 1] - shift) && (h[i] - shift) - j + 1 >= 0) {
			/*
			 * tenemos que sumar (i, j) a (i + 1, [0, h[i] - j]),
			 * usamos un arreglo de diferencias para actualizar el rango rápido
			 */
 
			int rb = (h[i] - shift) - j + 1;
 
			diff[0] += dp[j];
 
			if (diff[0] >= MOD) { diff[0] -= MOD; }
 
			// cuidado al aplicar módulo a valores negativos
			diff[rb] = (((diff[rb] - dp[j]) % MOD) + MOD) % MOD;
			j++;
		}
 
		dp[0] = diff[0];
 
		for (int j = 1; j <= MX_HUNGER; j++) {
			dp[j] = dp[j - 1] + diff[j];
 
			if (dp[j] >= MOD) { dp[j] -= MOD; }
 
			assert(dp[j] >= 0);
		}
 
		// reiniciamos el arreglo de diferencias
		for (int j = 0; j <= MX_HUNGER; j++) { diff[j] = 0; }
	}
 
	return dp[0];
}
 
int main() {
	cin >> n;
	h.reserve(n);
 
	int mn = MX_HUNGER;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		mn = min(mn, h[i]);
	}
 
	ll ans = 0;
	vector<int> h;
	vector<ll> dp(MX_HUNGER + 1);
	vector<ll> diff(MX_HUNGER + 2);
 
	if (n % 2 == 1) {
		/*
		 * no podemos asumir que todos los elementos pueden ser iguales a cero.
		 * en su lugar, tenemos que calcular la respuesta para todos los valores
		 * de hambre posibles.
		 */
		for (int i = 0; i <= mn; i++) { ans = (ans + ways_offset(i) + MOD) % MOD; }
	} else {
		ans = (ans + ways_offset(0) + MOD) % MOD;
	}
 
	cout << ans << endl;
}