Dada una array arr[] que tiene N enteros positivos y un número entero positivo H , la tarea es contar el máximo de ocurrencias de un valor del rango [L, R] al sumar arr[i] o arr[i] – 1 a X (inicialmente 0). El entero X debe ser siempre menor que H . Si es mayor que H , reemplaza X por X % H
Ejemplos:
Entrada: arr = {16, 17, 14, 20, 20, 11, 22}, H = 24, L = 21, R = 23
Salida: 3
Explicación:
Inicialmente X = 0.
Luego agregue arr[0] – 1 a X, ahora la X es 15. Esta X no es buena.
Luego agregue arr[1] – 1 a X, ahora X es 15 + 16 = 31. 31 % H = 7. Esta X tampoco es buena.
Luego agregue arr[2] a X, ahora X es 7 + 14 = 21. Esta X es buena.
Luego agregue arr[3] – 1 a X, ahora la X es (21 + 19) % H = 16. Esta X no es buena.
Luego agregue arr[4] a X, ahora la X es (16 + 20) % H = 12. Esta X no es buena.
Luego agregue arr[5] a X, ahora X es 12 + 11 = 23. Esta X es buena.
Luego agregue arr[6] a X, ahora X es 23 + 22 = 21. Esta X también es buena.
Entonces, el número máximo de bienes X en el ejemplo es 3.Entrada: arr = {1, 2, 3}, H = 5, L = 1, R = 2
Salida: 2
Enfoque: Este problema se puede resolver con programación dinámica . Mantenga una tabla dp[N+1][H] que represente las ocurrencias máximas de un elemento en el rango [L, R] al sumar i elementos. Para cada i -ésimo índice, calcule la frecuencia máxima posible que se puede obtener sumando arr[i] y arr[i] – 1. Una vez calculado para todos los índices, encuentre el máximo de la última fila de la array dp[][] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function that prints the number
// of times X gets a value
// between L and R
void goodInteger(int arr[], int n,
int h, int l, int r)
{
vector<vector<int> > dp(
n + 1,
vector<int>(h, -1));
// Base condition
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < h; j++) {
// Condition if X can be made
// equal to j after i additions
if (dp[i][j] != -1) {
// Compute value of X
// after adding arr[i]
int h1 = (j + arr[i]) % h;
// Compute value of X after
// adding arr[i] - 1
int h2 = (j + arr[i] - 1) % h;
// Update dp as the maximum value
dp[i + 1][h1]
= max(dp[i + 1][h1],
dp[i][j]
+ (h1 >= l
&& h1 <= r));
dp[i + 1][h2]
= max(dp[i + 1][h2],
dp[i][j]
+ (h2 >= l
&& h2 <= r));
}
}
}
int ans = 0;
// Compute maximum answer from all
// possible cases
for (int i = 0; i < h; i++) {
if (dp[n][i] != -1)
ans = max(ans, dp[n][i]);
}
// Printing maximum good occurrence of X
cout << ans << "\n";
}
// Driver Code
int main()
{
int A[] = { 16, 17, 14, 20, 20, 11, 22 };
int H = 24;
int L = 21;
int R = 23;
int size = sizeof(A) / sizeof(A[0]);
goodInteger(A, size, H, L, R);
return 0;
}
Java
// Java implementation of the
// above approach
class GFG{
// Function that prints the number
// of times X gets a value
// between L and R
static void goodInteger(int arr[], int n,
int h, int l, int r)
{
int [][]dp = new int[n + 1][h];
for(int i = 0; i < n; i++)
for(int j = 0; j < h; j++)
dp[i][j] = -1;
// Base condition
dp[0][0] = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < h; j++)
{
// Condition if X can be made
// equal to j after i additions
if (dp[i][j] != -1)
{
// Compute value of X
// after adding arr[i]
int h1 = (j + arr[i]) % h;
// Compute value of X after
// adding arr[i] - 1
int h2 = (j + arr[i] - 1) % h;
// Update dp as the maximum value
dp[i + 1][h1] = Math.max(dp[i + 1][h1],
dp[i][j] +
((h1 >= l &&
h1 <= r) ?
1 : 0));
dp[i + 1][h2] = Math.max(dp[i + 1][h2],
dp[i][j] +
((h2 >= l &&
h2 <= r) ?
1 : 0));
}
}
}
int ans = 0;
// Compute maximum answer from all
// possible cases
for(int i = 0; i < h; i++)
{
if (dp[n][i] != -1)
ans = Math.max(ans, dp[n][i]);
}
// Printing maximum good occurrence of X
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 16, 17, 14, 20, 20, 11, 22 };
int H = 24;
int L = 21;
int R = 23;
int size = A.length;
goodInteger(A, size, H, L, R);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach # Function that prints the number # of times X gets a value # between L and R def goodInteger(arr, n, h, l, r): dp = [[-1 for i in range(h)] for j in range(n + 1)] # Base condition dp[0][0] = 0 for i in range(n): for j in range(h): # Condition if X can be made # equal to j after i additions if(dp[i][j] != -1): # Compute value of X # after adding arr[i] h1 = (j + arr[i]) % h # Compute value of X after # adding arr[i] - 1 h2 = (j + arr[i] - 1) % h # Update dp as the maximum value dp[i + 1][h1] = max(dp[i + 1][h1], dp[i][j] + (h1 >= l and h1 <= r)) dp[i + 1][h2] = max(dp[i + 1][h2], dp[i][j] + (h2 >= l and h2 <= r)) ans = 0 # Compute maximum answer from all # possible cases for i in range(h): if(dp[n][i] != -1): ans = max(ans, dp[n][i]) # Printing maximum good occurrence of X print(ans) # Driver Code if __name__ == '__main__': A = [ 16, 17, 14, 20, 20, 11, 22 ] H = 24 L = 21 R = 23 size = len(A) goodInteger(A, size, H, L, R) # This code is contributed by Shivam Singh
C#
// C# implementation of the
// above approach
using System;
class GFG{
// Function that prints the number
// of times X gets a value
// between L and R
static void goodint(int []arr, int n,
int h, int l, int r)
{
int [,]dp = new int[n + 1, h];
for(int i = 0; i < n; i++)
for(int j = 0; j < h; j++)
dp[i, j] = -1;
// Base condition
dp[0, 0] = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < h; j++)
{
// Condition if X can be made
// equal to j after i additions
if (dp[i, j] != -1)
{
// Compute value of X
// after adding arr[i]
int h1 = (j + arr[i]) % h;
// Compute value of X after
// adding arr[i] - 1
int h2 = (j + arr[i] - 1) % h;
// Update dp as the maximum value
dp[i + 1, h1] = Math.Max(dp[i + 1, h1],
dp[i, j] +
((h1 >= l &&
h1 <= r) ?
1 : 0));
dp[i + 1, h2] = Math.Max(dp[i + 1, h2],
dp[i, j] +
((h2 >= l &&
h2 <= r) ?
1 : 0));
}
}
}
int ans = 0;
// Compute maximum answer from all
// possible cases
for(int i = 0; i < h; i++)
{
if (dp[n, i] != -1)
ans = Math.Max(ans, dp[n, i]);
}
// Printing maximum good occurrence of X
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 16, 17, 14, 20, 20, 11, 22 };
int H = 24;
int L = 21;
int R = 23;
int size = A.Length;
goodint(A, size, H, L, R);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the
// above approach
// Function that prints the number
// of times X gets a value
// between L and R
function goodInteger(arr, n, h, l, r)
{
let dp = new Array(n + 1);
for(var i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
for(let i = 0; i < n+1; i++)
for(let j = 0; j < h; j++)
dp[i][j] = -1;
// Base condition
dp[0][0] = 0;
for(let i = 0; i < n; i++)
{
for(let j = 0; j < h; j++)
{
// Condition if X can be made
// equal to j after i additions
if (dp[i][j] != -1)
{
// Compute value of X
// after adding arr[i]
let h1 = (j + arr[i]) % h;
// Compute value of X after
// adding arr[i] - 1
let h2 = (j + arr[i] - 1) % h;
// Update dp as the maximum value
dp[i + 1][h1] = Math.max(dp[i + 1][h1],
dp[i][j] +
((h1 >= l &&
h1 <= r) ?
1 : 0));
dp[i + 1][h2] = Math.max(dp[i + 1][h2],
dp[i][j] +
((h2 >= l &&
h2 <= r) ?
1 : 0));
}
}
}
let ans = 0;
// Compute maximum answer from all
// possible cases
for(let i = 0; i < h; i++)
{
if (dp[n][i] != -1)
ans = Math.max(ans, dp[n][i]);
}
// Printing maximum good occurrence of X
document.write(ans + "\n");
}
// Driver Code
let A = [ 16, 17, 14, 20, 20, 11, 22 ];
let H = 24;
let L = 21;
let R = 23;
let size = A.length;
goodInteger(A, size, H, L, R);
// This code is contributed by sanjoy_62
</script>
3
Complejidad de tiempo: O(N * H)
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA