Existe um problema padrão de DP semelhante ao SPOJ Farida?

Sim, Farida é semelhante a um problema padrão chamado Problema da Mochila 0-1.
De fato, Farida é uma versão mais fácil. Depois de resolver o Farida, sugiro que você experimente o SPOJ.com – Problema RPLB

Você pode encontrar informações sobre o problema da mochila aqui: Programação dinâmica | Conjunto 10 (problema da mochila 0-1) – GeeksforGeeks


De qualquer forma, a abordagem dp para esse problema será:

Aqui, [math] dp [i] [/ math] mantém o número ideal de moedas de ouro que ela pode carregar depois de alcançar o monstro [math] i [/ math]. [math] wt [i] [/ math] contém o número de moedas de ouro com o monstro [math] i [/ math].

Para a solução ideal, considere três casos:

1. Caso básico: para monstros [math] 0 [/ math], ela não pode escolher nenhuma moeda de ouro. Portanto, [math] ans = 0 [/ math].

2. Outro caso básico: para um monstro [math] 1 [/ math], ela terá que escolher o único monstro para o número máximo de moedas. Portanto, [math] ans = [/ math] número de moedas com o primeiro monstro.

3. Caso Geral: Aqui ela terá que escolher o máximo de duas opções:
a) pegue moedas do monstro [math] i [/ math]:
[math] ans = [/ math] moedas de [math] i [/ math] monster [math] + [/ math] solução ideal até [math] i-2 [/ math] monster
b) não pegue moedas do monstro [math] i [/ math]
[math] ans = [/ math] solução ideal até o monstro [math] i-1 [/ math]


memset (dp, 0, sizeof (dp)); // opt1
for (int i = 1; i <= monstros; i ++)
{
se (i == 1) dp [i] = peso [i]; // opt2
senão dp [i] = max (peso [i] + dp [i-2], dp [i-1]); // opt3
}


Além disso, você pode encontrar casos de teste para esse problema no SPOJ Toolkit: Code Test – FARIDA. Isso ajudará na verificação do seu código antes de enviar.

Espero que isto ajude!

As perguntas são iguais à soma máxima do problema em uma matriz quando não há dois elementos adjacentes que podem ser resolvidos via dp desta maneira:

dp [i] = soma máxima quando não há dois elementos adjacentes na sub-matriz a [1..i]
Assim, dp [i] = max (dp [i-1], dp [i-2] + a [i]);
ou seja, o máximo de situações em que incluímos o i-ésimo elemento ou o excluímos.

Esse problema também pode ser resolvido sem espaço extra, porém a lógica permanece a mesma.

More Interesting

Nos seguintes casos, o que é verdade na linguagem de programação C?

Existem algoritmos que executam [math] O (1 / n) [/ math]?

Por que a classificação rápida é chamada de 'rápida', mesmo quando possui complexidade O (n2) no pior dos casos?

Como escrever um programa que, com duas matrizes classificadas com N int valores, imprima todos os elementos que aparecem nas duas matrizes, na ordem classificada

Qual é o algoritmo mais fácil para encontrar o caminho mais curto em um robô seguidor de linha para iniciantes?

Quais são os algoritmos mais eficientes que resolvem de maneira ideal o cubo de Rubik?

Sphere Online Judge (SPOJ): Por que o código a seguir resulta em TLE? Quero saber como meu código pode ser otimizado para evitá-lo.

Qual é a diferença entre o Java SE, ou seja, Core Java, e estruturas e algoritmos de dados?

Qual é a diferença entre um algoritmo baseado em restrições e um algoritmo baseado em regras?

Quais são as perguntas clássicas que devem ser resolvidas no SPOJ?

Você pode compartilhar seu algoritmo de encontrar o comprimento do AP mais longo em um determinado array?

Qual é a diferença entre binário, algoritmo e linguagem de programação?

Qual seria a maneira mais eficiente de verificar se um determinado número é fatorial de algum número ou não?

Quais são alguns exemplos de algoritmos de negociação que funcionam para pequenos comerciantes, mas não para grandes instituições?

Quais são os algoritmos de nível básico com os quais devemos começar e quais são os algoritmos avançados que devemos estudar?