Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.
Se o problema se resume ao fato de que é necessário dividir a matriz em subsegmentos sem interseção (uma sequência de elementos consecutivos) de maneira ideal (ou contar o número de divisões adequadas), vale a pena tentar resolvê-lo usando programação dinâmica.
Um exemplo de esquema de solução é o seguinte:
dp[i] - resposta para os primeiros i elementos
Contando dp[i]: como estamos considerando apenas os primeiros i elementos, o i-ésimo elemento será o último, o que significa que este elemento estará no último subsegmento e, ao mesmo tempo, o mais à direita ali. Portanto, podemos iterar sobre o limite esquerdo do último subsegmento j. No processo de enumeração, calcularemos o valor deste subsegmento e, se estiver correto, recalcularemos dp[i] até dp[j - 1] e o valor do subsegmento [j;i].
Considere o seguinte problema simples: dado um array de números inteiros, você precisa dividi-lo em um número mínimo de subsegmentos sem interseção de modo que cada número seja incluído em algum subsegmento e cada subsegmento contenha os mesmos números. Por exemplo, para um array 1 2 2 3 3 3 2 1 1, a partição ideal se parece com isto: [1] [2 2] [3 3 3] [2] [1 1]. Essa tarefa é facilmente resolvida simplesmente passando pelo array (colocamos todos os mesmos elementos consecutivos em um subsegmento), mas vamos resolvê-la usando a programação dinâmica como exemplo.
int;
cin>> n;
// preenche array com 1-index
vetor arr(n + 1);
for (int i = 1; i <= n; i++)
cin>> arr[i];
// inicialmente define +oo para valores dp
vetor dp(n + 1, 1000000000);
// um array de comprimento zero não precisa ser dividido, então a resposta para ele é 0
dp[0] = 0;
// conta a resposta para dp[i] em i crescente
for (int i = 1; i <= n; i++) {
// atualmente arr[i] é o último elemento, então será o número mais à direita no último subsegmento
// percorre todas as opções de onde este último subsegmento começou
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// se você encontrar um elemento que não é igual ao último, o subsegmento conterá números diferentes e isso não se encaixa na condição
// não adianta continuar, porque deslocando a borda esquerda para a esquerda, este elemento não desaparecerá, então quebramos
quebrar;
}
// imagine que o último subsegmento foi [j;i]
// então você precisa pegar a partição ideal dos primeiros elementos j-1 e adicionar 1 (o próprio subsegmento [j; i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Se os elementos não pertencerem a nenhum dos subsegmentos, basta considerar a opção apropriada, pois dp[i] = dp[i - 1]
|
Se for necessário dividir a matriz em exatamente k subsegmentos, o segundo parâmetro é simplesmente adicionado na programação dinâmica - em quantos segmentos dividir.
Ou seja, agora vamos considerar o seguinte dp:
dp[i][j] é a resposta para os primeiros i elementos, se os dividirmos em exatamente j segmentos.
Cuidado com estados inválidos.
O recálculo da dinâmica é o mesmo, mas levando em consideração o segundo parâmetro. Ou seja, contando dp[i][k] e classificando pela borda esquerda do último subsegmento j, recalculamos dp[i][k] até dp[j - 1][k - 1] e o valor do segmento [j;i].
|
Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.
Se houver um conjunto de lacunas localizadas em algum eixo (geralmente o eixo do tempo ou índices de algum array) e você precisar escolher alguns deles de maneira ideal para que as lacunas selecionadas não se cruzem, tente usar a programação dinâmica .
Esquema de solução aproximada:
Inicialmente, classificamos as lacunas disponíveis pela borda direita. Vamos iniciar a seguinte dinâmica: dp[i] - a resposta para os primeiros i intervalos.
Vamos recalcular da seguinte forma: primeiro, considere a situação em que esse intervalo não será utilizado, depois é só dp[i] = dp[i-1]. Observe que isso garante que os valores de dp[i] não diminuam à medida que i cresce. E isso é lógico, porque. adicionando uma nova lacuna, não podemos piorar a resposta global: ou simplesmente ignoramos a nova lacuna ou construímos uma variante mais lucrativa usando-a. Agora, se quisermos usar o i-ésimo gap, podemos usar os gaps cujas bordas direitas são menores que a borda esquerda do gap atual, pois devemos escolher um conjunto de gaps não sobrepostos. Para fazer isso, inicialmente classificamos as lacunas pela borda direita, para que agora possamos encontrar com eficiência a posição necessária. Isso pode ser feito analiticamente, se possível, mas no caso geral é possível encontrar uma lacuna com uma pesquisa binária, cuja borda direita é menor que a borda esquerda da atual e, ao mesmo tempo, o máximo possível um. Queremos maximizar a borda certa por motivos gananciosos, porque conforme eu cresço, a resposta só pode aumentar. Assim, encontramos a posição p necessária e recalculamos dp[i] até dp[p] e o i-ésimo intervalo.
|