Red de conocimiento informático - Material del sitio web - Pregunta de calificación: Collar de energía

Pregunta de calificación: Collar de energía

Noip2006-1

Reimpreso de Universe Rookie

Collar de energía

(energy.pas/c/cpp)

Muy buena pregunta. Esta era la pregunta en la que tenía más confianza antes de que se anunciaran los resultados. Sin embargo, al final no respondí esta pregunta. No sé si estoy loco o si SDTSC está loco.

Evidentemente DP. Algunas personas dicen que esto es algo similar a la clásica "fusión de guijarros".

Utilizamos cuentas para dividir etapas. F[I,J] representa el valor máximo combinado desde la i-ésima cuenta hasta la j-ésima cuenta. tou[i] y wei[i] representan el número de cabeza y el número de cola de la cuenta i respectivamente. Podemos derivar fácilmente la ecuación de transformación dinámica:

F[I, J]=max(F[I,K] F[K 1,J] tou[i]*wei[k]*wei[ j]); (1≤i≤n, i≤j≤n, i≤k≤j-1)

Límite: F[I, I]=0

Finalmente ANS=F[1, n]

La complejidad temporal de dicho dp es O(n^3).

Necesitamos enumerar la posición del collar cortado cada vez. Siempre hay n formas de cortar, cada forma realiza DP una vez y actualiza el nudo óptimo. La complejidad del tiempo total es O (n ^ 4). Parece difícil manejar grandes cantidades de datos. . . .

Considere la optimización: la clave de este problema es linealizar la cadena para que la solución se pueda resolver en un dp. Entonces expandimos la matriz a n×2;

F[I, J]=max(F[I,K] F[K 1,J] tou[i]*wei[k]* wei [j]); (1≤i≤n, i≤j≤n+i, i≤k≤j-1)

Límite: F[I, I]=0

Finalmente ANS=max(F[i, i n-1]); (1≤i≤n)

De esta manera, dp puede resolver el problema de una vez y la complejidad del tiempo es O(n^3).

const maxn=100;

var tou, wei: matriz[1..2*maxn] de entero;

n, i, j, k , p: entero;

f: matriz[1..maxn*2, 1..maxn*2] de entero largo

max: entero largo

comenzar

asignar(entrada,'energía.in');

asignar(salida,'energía.salida');

reset(entrada);

readln(n);

for i:=1 to n do

comenzar

read(tou[i]);

tou[n i]:=tou[i];

end;

para i:=1 a n-1 hacer

comenzar

wei[i]:=tou[i 1];

wei[i n]:=wei[i];

fin;

p>

wei[n]:=tou[1];

wei[2*n]:=wei[n];

cerrar( entrada);

wei[2*n]:=wei[n];

cerrar(entrada);

p>

fillchar(f ,sizeof(f),0);

para p:=1 a n-1 hacer

para i:=1 a 2*n -2 hacer

comenzar

j:=i p;

si jgt; 2*n-1 entonces romper

for k :=i a j-1

comenzar

max:=f[i,k] f[k 1,j] tou[i]*wei[k]*wei [j];

si f[i,j]lt;max entonces

f[i,j]:=max;

fin;

p>

end;

for i:=1 to n do

for j:=i to n i do

if ilt; j then

p>

for k:=i to j-1 do

comenzar

max:=f[i,k] f[k 1,j] tou [i] *wei[k]*wei[j];

si maxgt; f[i, j] entonces f[i, j]:=max

fin; >

max:=0;

para i:=1 a n hacer

si f[i,i n-1]gt;max entonces max: =f[ i,i n-1];

reescribir(salida);

escribirn(max);

cerrar(salida);

fin.