Dada una array arr[] que consta de valores (0, 1, 2, 3) de longitud N, que representan el tipo de trabajo que se puede realizar en cualquier i-ésimo día, de modo que la tarea sea del tipo A o del tipo B. Cada valor en la array se define como:
0 : no hay tareas disponibles.
1 – La tarea de tipo B está disponible.
2 – La tarea de tipo A está disponible.
3 : tanto la tarea A como la tarea B están disponibles.
Si no se puede realizar el mismo tipo de tarea durante dos días consecutivos, la tarea consiste en minimizar el número de días en los que no se realizará ninguna tarea.
Ejemplos:
Entrada : N = 4, arr = {0, 1, 3, 2}
Salida : 2
Explicación : Los siguientes son los tipos de tareas realizadas en cada día.
El primer día no hay tareas, por lo que no hace nada y la cuenta se convierte en 1.
El segundo día, realiza una tarea de tipo B.
El tercer día hay ambas tareas, pero como había hecho una tarea de tipo B el día anterior . por lo que realiza la tarea A.
El último día hay una tarea A disponible pero había realizado la misma tarea el día anterior, por lo que no hace nada y la cuenta se convierte en 2.
Por lo tanto, 2 es la respuesta final.Entrada: N = 8, arr[] = {0, 1, 3, 2, 0, 2, 3, 3}
Salida: 3
Enfoque ingenuo : este problema se puede resolver utilizando la recursividad . Siga los pasos a continuación para resolver el problema dado.
- Declare una variable, digamos count = 0, para almacenar la respuesta.
- Si arr[i]=0, no hay ninguna tarea, así que no haga nada y aumente la cuenta.
- Si arr[i]=1, solo la tarea B está disponible, si la tarea del último día fue B, entonces no haga nada y aumente el conteo; de lo contrario, realice la tarea B.
- Si arr[i]=2, solo la tarea A está disponible, si la tarea del último día fue A, entonces no haga nada y aumente el conteo; de lo contrario, realice la tarea A.
- Si arr[i]=3, y la tarea del último día fue A, entonces realice la tarea B, si la tarea del último día fue B, entonces realice la tarea A, de lo contrario, realice la tarea que minimizará la cantidad de días en los que no se realiza ninguna tarea.
- Use una variable last para realizar un seguimiento de la tarea del día anterior, que puede tomar los siguientes valores:
- 0: ninguna tarea realizada.
- 1 – la tarea de tipo A realizada
- 2 – la tarea de tipo B realizada
A continuación se muestra la implementación del enfoque anterior.
C++
#include <bits/stdc++.h>
using namespace std;
int solve(int a[], int last, int n)
{
// Base case
if (n == 0)
return 0;
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return 1 + solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task B
return solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A
// so can't perform it again
if (last == 1)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task A
return solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
// Perform task A
return solve(a, 1, n - 1);
else
// Perform the minimum among both
return min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
int main()
{
// Number of days
int N = 4;
int arr[] = { 0, 1, 3, 2 };
cout << solve(arr, 0, N) << endl;
return 0;
}
Java
import java.util.*;
public class GFG
{
static int solve(int []a, int last, int n)
{
// Base case
if (n == 0)
return 0;
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return 1 + solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task B
return solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A
// so can't perform it again
if (last == 1)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task A
return solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
// Perform task A
return solve(a, 1, n - 1);
else
// Perform the minimum among both
return Math.min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
public static void main(String args[])
{
// Number of days
int N = 4;
int []arr = { 0, 1, 3, 2 };
System.out.println(solve(arr, 0, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
def solve(a, last, n): # Base case if (n == 0): return 0 # Condition 1 (no task) so does nothing if (a[n - 1] == 0): # Increase count return 1 + solve(a, 0, n - 1) # Condition 2 (only task B) elif (a[n - 1] == 1): # Last task is of type B # so can't perform it again if (last == 2): # Increase count return 1 + solve(a, 0, n - 1) else: # Perform task B return solve(a, 2, n - 1) # Condition 3 (only task A ) elif (a[n - 1] == 2): # Last task is of type A # so can't perform it again if (last == 1): # Increase count return 1 + solve(a, 0, n - 1) else: # Perform task A return solve(a, 1, n - 1) # Condition 4 (both task A and B) else: # Last task is of type A if (last == 1): # Perform task B return solve(a, 2, n - 1) # Last task is of type B elif (last == 2): # Perform task A return solve(a, 1, n - 1) else: # Perform the minimum among both return min(solve(a, 2, n - 1), solve(a, 1, n - 1)) # Number of days N = 4 arr = [0, 1, 3, 2] print(solve(arr, 0, N)) # This code is contributed by gfgking.
C#
using System;
class GFG
{
static int solve(int []a, int last, int n)
{
// Base case
if (n == 0)
return 0;
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return 1 + solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task B
return solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A
// so can't perform it again
if (last == 1)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task A
return solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
// Perform task A
return solve(a, 1, n - 1);
else
// Perform the minimum among both
return Math.Min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
public static void Main()
{
// Number of days
int N = 4;
int []arr = { 0, 1, 3, 2 };
Console.Write(solve(arr, 0, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
function solve(a, last, n)
{
// Base case
if (n == 0)
return 0;
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return 1 + solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task B
return solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A
// so can't perform it again
if (last == 1)
// Increase count
return 1 + solve(a, 0, n - 1);
else
// Perform task A
return solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
// Perform task A
return solve(a, 1, n - 1);
else
// Perform the minimum among both
return Math.min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
// Number of days
let N = 4;
let arr = [ 0, 1, 3, 2 ];
document.write(solve(arr, 0, N));
// This code is contributed by Samim Hossain Mondal.
</script>
Complejidad temporal: O(2 n )
Espacio auxiliar: O(1)
Producción
2
Enfoque eficiente: Para optimizar el enfoque anterior, se puede utilizar la programación dinámica . Utilice la memorización para almacenar el estado anterior de modo que esos estados anteriores se puedan utilizar para calcular resultados adicionales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
int dp[101][3];
int solve(int a[], int last, int n)
{
// Base case
if (n == 0)
return 0;
// If the value is pre-calculated return it
if (dp[n][last] != -1)
return dp[n][last];
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A so can't
if (last == 1)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task A
return dp[n][last]
= solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
return dp[n][last]
= solve(a, 1, n - 1);
// Perform task A
else
// Perform the minimum among both
return dp[n][last]
= min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
int main()
{
int N = 4;
int arr[] = { 0, 1, 3, 2 };
// Initialize the space with -1
memset(dp, -1, sizeof(dp));
cout << solve(arr, 0, N) << endl;
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
public class GFG
{
static int dp[][] = new int[101][3];
static int solve(int []a, int last, int n)
{
// Base case
if (n == 0)
return 0;
// If the value is pre-calculated return it
if (dp[n][last] != -1)
return dp[n][last];
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A so can't
if (last == 1)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task A
return dp[n][last]
= solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
return dp[n][last]
= solve(a, 1, n - 1);
// Perform task A
else
// Perform the minimum among both
return dp[n][last]
= Math.min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
public static void main(String args[])
{
// Number of days
int N = 4;
int []arr = { 0, 1, 3, 2 };
for(int i = 0; i < 101; i++) {
for(int j = 0; j < 3; j++) {
dp[i][j] = -1;
}
}
System.out.println(solve(arr, 0, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 program to implement # the above approach dp = [0] * 101 def solve(a, last, n): # Base case if (n == 0): return 0 # If the value is pre-calculated return it if (dp[n][last] != -1): return dp[n][last] # Condition 1 (no task) so does nothing if (a[n - 1] == 0): # Increase count dp[n][last] = 1 + solve(a, 0, n - 1) return dp[n][last] # Condition 2 (only task B) elif (a[n - 1] == 1): # Last task is of type B # so can't perform it again if (last == 2): # Increase count dp[n][last] = 1 + solve(a, 0, n - 1) return dp[n][last] else: # Perform task B dp[n][last] = solve(a, 2, n - 1) return dp[n][last] # Condition 3 (only task A ) elif (a[n - 1] == 2): # Last task is of type A so can't if (last == 1): # Increase count dp[n][last] = 1 + solve(a, 0, n - 1) return dp[n][last] else: dp[n][last] = solve(a, 1, n - 1) # Perform task A return dp[n][last] # Condition 4 (both task A and B) else: # Last task is of type A if (last == 1): dp[n][last] = solve(a, 2, n - 1) # Perform task B return dp[n][last] # Last task is of type B elif (last == 2): dp[n][last] = solve(a, 1, n - 1) return dp[n][last] # Perform task A else: dp[n][last] = min(solve(a, 2, n - 1), solve(a, 1, n - 1)) # Perform the minimum among both return dp[n][last] # Driver code N = 4 arr = [ 0, 1, 3, 2 ] # Initialize the space with -1 for i in range(len(dp)): dp[i] = [-1] * 3 print(solve(arr, 0, N)) # This code is contributed by Saurabh Jaiswal
C#
// C# Program to implement
// the above approach
using System;
class GFG
{
static int [,]dp = new int[101, 3];
static int solve(int []a, int last, int n)
{
// Base case
if (n == 0)
return 0;
// If the value is pre-calculated return it
if (dp[n, last] != -1)
return dp[n, last];
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return dp[n, last] = 1
+ solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1) {
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return dp[n, last] = 1
+ solve(a, 0, n - 1);
else
// Perform task B
return dp[n, last]
= solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2) {
// Last task is of type A so can't
if (last == 1)
// Increase count
return dp[n, last] = 1
+ solve(a, 0, n - 1);
else
// Perform task A
return dp[n, last]
= solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else {
// Last task is of type A
if (last == 1)
// Perform task B
return dp[n, last]
= solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
return dp[n, last]
= solve(a, 1, n - 1);
// Perform task A
else
// Perform the minimum among both
return dp[n, last]
= Math.Min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
public static void Main()
{
// Number of days
int N = 4;
int []arr = { 0, 1, 3, 2 };
for(int i = 0; i < 101; i++) {
for(int j = 0; j < 3; j++) {
dp[i, j] = -1;
}
}
Console.Write(solve(arr, 0, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let dp = new Array(101)
function solve(a, last, n)
{
// Base case
if (n == 0)
return 0;
// If the value is pre-calculated return it
if (dp[n][last] != -1)
return dp[n][last];
// Condition 1 (no task) so does nothing
if (a[n - 1] == 0) {
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
}
// Condition 2 (only task B)
else if (a[n - 1] == 1)
{
// Last task is of type B
// so can't perform it again
if (last == 2)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
}
// Condition 3 (only task A )
else if (a[n - 1] == 2)
{
// Last task is of type A so can't
if (last == 1)
// Increase count
return dp[n][last] = 1
+ solve(a, 0, n - 1);
else
// Perform task A
return dp[n][last]
= solve(a, 1, n - 1);
}
// Condition 4 (both task A and B)
else
{
// Last task is of type A
if (last == 1)
// Perform task B
return dp[n][last]
= solve(a, 2, n - 1);
// Last task is of type B
else if (last == 2)
return dp[n][last]
= solve(a, 1, n - 1);
// Perform task A
else
// Perform the minimum among both
return dp[n][last]
= min(solve(a, 2, n - 1),
solve(a, 1, n - 1));
}
}
let N = 4;
let arr = [ 0, 1, 3, 2 ];
// Initialize the space with -1
for(let i=0;i<dp.length;i++)
{
dp[i] = new Array(3).fill(-1);
}
document.write(solve(arr, 0, N) + "<br>")
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de tiempo: O(N), donde N es el tamaño de arr[].
Espacio auxiliar: O(N), donde N es el tamaño de arr[].