Ayuda en un problema de DP

Question

Estoy tratando de resolver un problema de SPOJ (link), que se puede describir brevemente así: Dado n intervalos, cada uno con un entero de principio y fin, y dado el final con tiempo máximo (vamos a llamarlo max_end), encuentre de cuántas maneras puede elegir un conjunto de intervalos que cubra 1 ... max_end. Los intervalos pueden superponerse. Intenté un DP; primero ordenar por hora de finalización, luego dp [i] es un par, donde dp [i] .primero es el número mínimo de intervalos necesarios para cubrir 1 ... fin [i] último uso del intervalo i y dp [i] .segundo es el número de formas de hacerlo. Aquí está mi bucle DP principal:

for(int i = 1; i < n; i ++) { 
    for(int j = 0; j < i; j ++) { 
     if(! (x[ j ].end >= x[ i ].start - 1)) 
      continue; 
     if(dp[ j ].first + 1 < dp[ i ].first) { 
      dp[ i ].first = dp[ j ].first + 1; 
      dp[ i ].second = dp[ j ].second; 
     } 
     else if(dp[ j ].first + 1 == dp[ i ].first) { 
      dp[ i ].second += dp[ j ].second; 
     } 
    } 
} 

Lamentablemente, no funcionó. ¿Alguien puede decirme dónde tengo un error? ¡Gracias por adelantado! :)

Answer 1

no estoy seguro de que consiga su idea solución, pero que describen mi solución de CA:

estoy usando la función de memorización, pero se puede volver a escribir utilizando no recurcive DP.

Digamos que tenemos nuestros intervalos en orden

par un [100]; donde a [i] .primero comienza el intervalo y un [i] .segundo es el final del intervalo.

Ordene esta matriz por begin first (comportamiento predeterminado del algoritmo stl sort con el comparador de pares predeterminado).

Ahora imagina que estamos 'poniendo' intervalos uno por uno de principio a fin.

let f (int x, int prev) devuelve el número de formas de finalizar el llenado si actualmente el último intervalo es x y el anterior es 'prev'.

vamos a calcular de la siguiente manera:

int f(int x, int prev) { 
    // if already calculated dp[x][prev], return it. Otherwise, calculate it 
    if (dp[x][prev] != -1) { 
    return dp[x][prev]; 
    } 
    if (a[x].second == m) { 
    return dp[x][prev] = 1; // it means - X is last interval in day 
    } 
    else { 
    dp[x][prev] = 0; 
    for (int i = x + 1; i < n; ++i) { // try to select next interval 
     if (a[i].first <= a[x].second && // there must be not empty space after x interval 
      a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless 
      a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless 
      a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless. 
     dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000; 
     } 
    } 
    } 
    return dp[x][prev]; 
} 

Después de que tenemos que llamar a esta función para cada par de intervalos, primero de los cuales se inicia en 0 y el segundo está conectado con el primero:

for (int i = 0; i < n; ++i) { 
    if (a[i].first == 0) { 
    for (int j = i + 1; j < n; ++j) { 
     if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless 
      a[j].first <= a[i].second && // there must be no space after i interval 
      a[j].second > a[i].second) { // in opposite case j will be useless 
      res = (res + f(j, i)) % 100000000; 
     } 
    } 
    // also we need to check the case when we use only one interval: 
    if (a[i].second == m) { 
     res = (res + 1) % 100000000; 
    } 
    } 
} 

Después de eso solo tenemos que imprimir la res.