Respuestas detalladas a la segunda pregunta de las semifinales del grupo de mejora NOIP2005
Supongamos que f(i) representa el número de piedras pisadas al menos al alcanzar la coordenada I.
R(i) indica si hay una piedra en la coordenada I. Si hay una piedra, r(i)=1, de lo contrario r(i)=0.
F(i)=min{f(j)}+r(i), donde s
límite f(0)=0
Respuesta= min{f(i)}, donde I>=L
La complejidad temporal de este algoritmo es O(L*(t-s)).
Análisis en profundidad:
De forma intuitiva, no necesitamos planificar dinámicamente una gran superficie sin piedras.
Se puede demostrar que cuando el área en blanco es mayor que un cierto máximo, la rana definitivamente puede saltar de un extremo del área al otro.
De hecho, para el intervalo de salto [s, t], max
Entonces podemos comprimir el área en blanco de la longitud >:max de cada párrafo a la longitud de máx. De esta forma, el L' total es solo m * max
De esta forma, la complejidad de la programación dinámica anterior es O(L'*(t-s)), y la solución se puede obtener dentro de un tiempo limitado.
Este análisis fue realizado por Yao Jinyu, el único ganador de NOIP2005 (recomendado para la Universidad de Pekín): Changsha Yali Middle School.
[Análisis del problema]
A primera vista, este problema es un problema de búsqueda típico. Ve de un lado al otro del río y busca la menor cantidad de rocas que puedas pisar. Pero desde la perspectiva del rango de datos. 1...109 longitudes de puente. Incluso el algoritmo O(n) no puede resolver la respuesta en un segundo.
Si buscas piedras, el método es más difícil. Para ello se deben tener en cuenta las piedras continuas antes y después. Cámbialo de otra manera. Usando programación dinámica, la complejidad temporal de un medidor dinámico unidimensional con piedras escalonadas es O(n2). Como máximo sólo hay 100×100 de tiempo. Pero dividir los estados de esta manera es muy complicado. Porque la distribución de los cálculos es irregular y tiene secuelas.
Así que tenemos que volver atrás y buscar. Encontrar piedras puede ser tan irregular como las reglas del movimiento. Buscamos la longitud de un puente y luego añadimos una poda inteligente para resolverlo en una fracción de tiempo. Se le puede llamar O(m2). [Nota: esta supuesta palabra se ha convertido en una palabra popular en Hunan OI este siglo]
[Realización del tema]
Busca primero la hora. La complejidad del tiempo es O (L). De un lado al otro del puente, no hay más de 100 piedras de por medio. Supongamos que la longitud del puente es la mayor (109) y el número de piedras también es el mayor (100). En este caso, debe haber muchas "barras vacías" (espacios en blanco en las dos piedras) en el medio. Si se omiten durante el procesamiento, solo hay m operaciones. La clave es encontrar todas las "barras vacías" que se puedan omitir.
Primero podemos encontrar todas las posibilidades para que la rana salte y luego encontrar las "barras vacías" que se pueden ignorar.
[Algoritmo especial]
A[i]: El número mínimo de piedras en la primera coordenada I. El número inicial es el número de piedras en la coordenada I.
B[i]: Las coordenadas de la piedra Ith.
Indicador de movimiento
a[0]= 0;
Derecha n>=t
a[n]=min{ a[n]+a[n-s], a[n]+a[n-s-1],..., a[n]+a[n-t]}
Lado derecho s =
a[n]=max{a[n]+a[n-s], a[n]+a[n-s-1],..., a[n]+a[0]}
Sin embargo, debido a la n grande, el indicador de acción directa expirará. Entonces n necesita ser comprimido.
Observando las coordenadas, podemos encontrar que si b[I]-b[I-1]>t, obviamente para b[I-1]+t
Ten en cuenta que Durante el proceso de cálculo, debido a que algunas coordenadas nunca se pueden alcanzar, es necesario utilizar la matriz booleana c [n] para juzgar. El método es que para c[n], si 0;s, c[n-t], c[n-t+1],..., c[n-s] son todos falsos, entonces c[n] también es falso.
Programa:
var f:array [0..9] longword
ts, piedra:array [0..longint 100];
j, I, s, t, l: longint;
k, os: byte;
tmp: palabra larga
Función gbs; (l, r:byte):palabra larga;
var i:byte;
Inicio
GBS:= 1;
for I:= l to r do GBS:= GBS * I;
Fin;
Inicio
Asignación (entrada, ' río . en ');
Asignación (salida, ' río . salida ');
Restablecer (entrada);
Reescribir (salida
filldword); (f, sizeof(f) div 4, maxlongint);
readln(l);
readln(s, t, piedra[0]);
para I:= 1 a piedra[0] lea(piedra[I]);
Para i:= 1 a piedra[0] haga
para j:=1 para i-1 hacer
si piedra[j]>piedra[i] entonces inicie tmp:= piedra[I];piedra[I]:= piedra[j]; tmp; fin;
ts[0]:= piedra[0];
ts[1]:= piedra[1]mod(GBS(s , t));
Si ts[1]=0 entonces ts[1]:= t;
Para i:=2 a piedra[0] haz
Iniciar
ts[I]:= ts[I-1]+(piedra[I]-piedra[I-1])mod(GBS(s,t));
if ( ts[i]=ts[i-1]) entonces ts[I]:= ts[I]+t;
if(piedra[I]-piedra[I- 1]<& gt1 ) y (ts[i]=ts[i-1]+1) entonces ts[I]:= ts[I]+t;
Fin;
l:= ts[ts[0]]+(l-s-piedra[piedra[0]])mod s+t;
Piedra:= ts
f [0]:= 0;
Porque quiero
Iniciar
OS:= 0;
for k:= 1 to stone[0]do if stone[k]= Luego inicio OS:= 1; fin de la interrupción;
tmp:= maxlongint;
for j:=i-t to i-s do
Iniciar
Si j & lt0 entonces continuar
Si j & gt entonces rompo
Si tmp & gtf[j mod 10]+os entonces; tmp:= f[j mod 10]+OS;
Fin;
f[I mod 10]:= tmp;
Fin;
j:= maxlongint;
para I:= l-t a l hacer si j & gt; f[i mod 10] entonces j:= f[I mod 10 ];
writeln(j);
Cerrar (salida);
Fin.