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
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.