Dadas dos arrays A[] y B[], ambas compuestas por N enteros, la tarea es encontrar el número de arrays no decrecientes de tamaño N que se pueden formar de modo que cada elemento de la array se encuentre en el rango [A[i], B[yo]] .
Ejemplos:
Entrada: A[] = {1, 1}, B[] = {2, 3}
Salida : 5
Explicación:
El número total de arrays válidas es {1, 1}, {1, 2}, {1, 3} , {2, 2}, {2, 3}. Por lo tanto, el conteo de dichas arrays es 5.Entrada: A[] = {3, 4, 5}, B[] = {4, 5, 6}
Salida: 8
Enfoque: El problema dado se puede resolver usando Programación Dinámica y Suma de Prefijos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D dp[][] con valores 0 , donde dp[i][j] denota la array válida total hasta la posición i y con el elemento actual como j . Inicialice dp[0][0] como 1 .
- Inicialice una array 2D pref[][] con valores 0 para almacenar la suma del prefijo de la array .
- Iterar sobre el rango [0, B[N – 1]] usando la variable i y establecer el valor de pref[0][i] como 1 .
- Iterar sobre el rango [1, N] usando la variable i y realizar los siguientes pasos:
- Iterar sobre el rango [A[i – 1], B[i – 1]] usando la variable j e incrementar el valor de dp[i][j] por pref[i – 1][j] y aumentar el valor de preferencia[i][j] por dp[i][j] .
- Itere sobre el rango [0, B[N – 1]] usando la variable j y si j es mayor que 0 , actualice la tabla de suma de prefijos incrementando el valor de pref[i][j] por pref[i][j – 1] .
- Inicialice la variable ans como 0 para almacenar el recuento resultante de arrays formadas.
- Iterar sobre el rango [A[N – 1], B[N – 1]] usando la variable i y agregar el valor de dp[N][i] a la variable ans .
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the total number
// of possible valid arrays
int totalValidArrays(int a[], int b[],
int N)
{
// Make a 2D DP table
int dp[N + 1][b[N - 1] + 1];
// Make a 2D prefix sum table
int pref[N + 1][b[N - 1] + 1];
// Initialize all values to 0
memset(dp, 0, sizeof(dp)),
memset(pref, 0, sizeof(pref));
// Base Case
dp[0][0] = 1;
// Initialize the prefix values
for (int i = 0; i <= b[N - 1]; i++) {
pref[0][i] = 1;
}
// Iterate over the range and update
// the dp table accordingly
for (int i = 1; i <= N; i++) {
for (int j = a[i - 1];
j <= b[i - 1]; j++) {
dp[i][j] += pref[i - 1][j];
// Add the dp values to the
// prefix sum
pref[i][j] += dp[i][j];
}
// Update the prefix sum table
for (int j = 0; j <= b[N - 1]; j++) {
if (j > 0) {
pref[i][j] += pref[i][j - 1];
}
}
}
// Find the result count of
// arrays formed
int ans = 0;
for (int i = a[N - 1];
i <= b[N - 1]; i++) {
ans += dp[N][i];
}
// Return the total count of arrays
return ans;
}
// Driver Code
int main()
{
int A[] = { 1, 1 };
int B[] = { 2, 3 };
int N = sizeof(A) / sizeof(A[0]);
cout << totalValidArrays(A, B, N);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to count the total number
// of possible valid arrays
static int totalValidArrays(int a[], int b[],
int N)
{
// Make a 2D DP table
int dp[][] = new int[N + 1][b[N - 1] + 1];
// Make a 2D prefix sum table
int pref[][] = new int[N + 1][b[N - 1] + 1];
// Initialize all values to 0
for (int i = 0; i < N + 1; i++)
for (int j = 0; j < b[N - 1] + 1; j++)
dp[i][j] = 0;
for (int i = 0; i < N + 1; i++)
for (int j = 0; j < b[N - 1] + 1; j++)
pref[i][j] = 0;
// Base Case
dp[0][0] = 1;
// Initialize the prefix values
for (int i = 0; i <= b[N - 1]; i++) {
pref[0][i] = 1;
}
// Iterate over the range and update
// the dp table accordingly
for (int i = 1; i <= N; i++) {
for (int j = a[i - 1];
j <= b[i - 1]; j++) {
dp[i][j] += pref[i - 1][j];
// Add the dp values to the
// prefix sum
pref[i][j] += dp[i][j];
}
// Update the prefix sum table
for (int j = 0; j <= b[N - 1]; j++) {
if (j > 0) {
pref[i][j] += pref[i][j - 1];
}
}
}
// Find the result count of
// arrays formed
int ans = 0;
for (int i = a[N - 1];
i <= b[N - 1]; i++) {
ans += dp[N][i];
}
// Return the total count of arrays
return ans;
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 1, 1 };
int B[] = { 2, 3 };
int N = A.length;
System.out.println(totalValidArrays(A, B, N));
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach # Function to count the total number # of possible valid arrays def totalValidArrays(a, b, N): # Make a 2D DP table dp = [[0 for _ in range(b[N - 1] + 1)] for _ in range(N + 1)] # Make a 2D prefix sum table pref = [[0 for _ in range(b[N - 1] + 1)] for _ in range(N + 1)] # Base Case dp[0][0] = 1 # Initialize the prefix values for i in range(0, b[N - 1] + 1): pref[0][i] = 1 # Iterate over the range and update # the dp table accordingly for i in range(1, N + 1): for j in range(a[i - 1], b[i - 1] + 1): dp[i][j] += pref[i - 1][j] # Add the dp values to the # prefix sum pref[i][j] += dp[i][j] # Update the prefix sum table for j in range(0, b[N - 1] + 1): if (j > 0): pref[i][j] += pref[i][j - 1] # Find the result count of # arrays formed ans = 0 for i in range(a[N - 1], b[N - 1] + 1): ans += dp[N][i] # Return the total count of arrays return ans # Driver Code if __name__ == "__main__": A = [1, 1] B = [2, 3] N = len(A) print(totalValidArrays(A, B, N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the total number
// of possible valid arrays
static int totalValidArrays(int[] a, int[] b, int N)
{
// Make a 2D DP table
int[,] dp = new int[N + 1, b[N - 1] + 1];
// Make a 2D prefix sum table
int[,] pref = new int[N + 1, b[N - 1] + 1];
// Initialize all values to 0
for (int i = 0; i < N + 1; i++)
for (int j = 0; j < b[N - 1] + 1; j++)
dp[i, j] = 0;
for (int i = 0; i < N + 1; i++)
for (int j = 0; j < b[N - 1] + 1; j++)
pref[i, j] = 0;
// Base Case
dp[0, 0] = 1;
// Initialize the prefix values
for (int i = 0; i <= b[N - 1]; i++) {
pref[0, i] = 1;
}
// Iterate over the range and update
// the dp table accordingly
for (int i = 1; i <= N; i++) {
for (int j = a[i - 1];
j <= b[i - 1]; j++) {
dp[i, j] += pref[i - 1, j];
// Add the dp values to the
// prefix sum
pref[i, j] += dp[i, j];
}
// Update the prefix sum table
for (int j = 0; j <= b[N - 1]; j++) {
if (j > 0) {
pref[i, j] += pref[i, j - 1];
}
}
}
// Find the result count of
// arrays formed
int ans = 0;
for (int i = a[N - 1];
i <= b[N - 1]; i++) {
ans += dp[N, i];
}
// Return the total count of arrays
return ans;
}
// Driver Code
public static void Main ()
{
int[] A = { 1, 1 };
int[] B = { 2, 3 };
int N = A.Length;
Console.WriteLine(totalValidArrays(A, B, N));
}
}
// This code is contributed by Saurabh
Javascript
<script>
// JavaScript program for the above approach
// Function to count the total number
// of possible valid arrays
const totalValidArrays = (a, b, N) => {
// Make a 2D DP table
let dp = new Array(N + 1).fill(0).map(() => new Array(b[N - 1] + 1).fill(0));
// Make a 2D prefix sum table
let pref = new Array(N + 1).fill(0).map(() => new Array(b[N - 1] + 1).fill(0));
// Base Case
dp[0][0] = 1;
// Initialize the prefix values
for (let i = 0; i <= b[N - 1]; i++) {
pref[0][i] = 1;
}
// Iterate over the range and update
// the dp table accordingly
for (let i = 1; i <= N; i++) {
for (let j = a[i - 1];
j <= b[i - 1]; j++) {
dp[i][j] += pref[i - 1][j];
// Add the dp values to the
// prefix sum
pref[i][j] += dp[i][j];
}
// Update the prefix sum table
for (let j = 0; j <= b[N - 1]; j++) {
if (j > 0) {
pref[i][j] += pref[i][j - 1];
}
}
}
// Find the result count of
// arrays formed
let ans = 0;
for (let i = a[N - 1];
i <= b[N - 1]; i++) {
ans += dp[N][i];
}
// Return the total count of arrays
return ans;
}
// Driver Code
let A = [1, 1];
let B = [2, 3];
let N = A.length;
document.write(totalValidArrays(A, B, N));
// This code is contributed by rakeshsahni
</script>
Producción:
5
Complejidad temporal: O(N*M), donde M es el último elemento del arreglo B[].
Espacio Auxiliar: O(N*M), donde M es el último elemento del arreglo B[].
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA