Runda 3: Baner (rozwiązanie)

Autor zadania: Jarosław Gomułka

Zauważmy że istnieje optymalne rozwiązanie w którym wszystkie wykonywacje operacje sa rozłączne tzn:

• Nie usuniemy żadnej litery z dodanego wcześniej fragmentu. Moglibyśmy tej litery nie dodawać i później nie usuwać, koszt byłby niewiększy.
• Dodawany fragment nie zostanie dodany pomiędzy 2 litery z dodanego wczesniej fragmentu, moglibyśmy dodać całość jako jeden fragment bez żadnych strat.

W rozwiązaniu wzorcowym szukamy najlepszego ciągu operacji które są rozłączne.
Rozłączność gwarantuje nam, że możemy wykonywać ciąg operacji rozłącznych w dowolnej kolejności.
Wykonujmy je w kolejności od tych które zmieniają pierwsze litery ciągu aż do tych które zmieniają ostatnie litery ciągu.

Popatrzmy na funkcje definującą koszt wykonania operacji.
Możemy ją przedefiniować na następującą:
Inicjalizacja do dodania/usunięcia pojedynczego fragemntu ma koszt X
Koszt dodania/usunięcia każdej kolejnej litery to Y

Zdefiniujmy teraz tablice DP:

• DP[x][y][0] <- koszt przekształcenia słowa A[1..x] w B[1..y]
• DP[x][y][1] <- koszt przekształcenia słowa A[1..x] w B[1..y] przy założeniu, że mamy już zainicjalizowaną operacje dodawania
• DP[x][y][2] <- koszt przekształcenia słowa A[1..x] w B[1..y] przy założeniu, że mamy już zainicjalizowaną operacje usuwania
• Słowo[1..0] to słowo puste

Chcemy obliczyć DP[n][m][0]. Zastanówmy się jakie operacje mogłyby być wykonywane jako ostatnie:

• Jeśli A[n] == B[m] to DP[n][m][0] mogło powstać poprzez pozostawienie ostatniej litery nietchniętej, czyli koszt edycji w takim wypadku to DP[n-1][m-1][0]
• Mogliśmy zakończyć dodawanie fragemntu. Wynik to DP[n][m-1][1]+Y
• Mogliśmy zakończyć usuwanie fragmentu. Wynik to DP[n-1][m][2]+Y

To są wszystkie możliwości, wystarczy wziąć minimum z kosztów tych 3 przypadków.

DP[n][m][1] mogło być uzyskane na 2 możliwości:

• Inicjalizujemy dodawanie fragmentu: koszt to DP[n][m][0] + X
• Dodaliśmy tą litere jako kolejną: koszt to DP[n][m-1][1] + Y

DP[n][m][2] analogicznie również mogłobyć uzyskane na 2 możliwości:

• Inicjalizujemy usuwanie fragmentu: koszt to DP[n][m][0] + X
• Usuneliśmy tą litere jako kolejną: koszt to DP[n-1][m][2] + Y

W ten sposób mamy rekurencje na DP[n][m][0] DP[n][m][1] DP[n][m][2]
Teraz wystarczy zauważyć, że kolejne wartości DP możemy obliczać w następującej kolejności:

for(int i=0; i<=n; i++)
for(int j=0; j<=m; j++)
for(int k=0; k<=2; k++)
Oblicz DP[i][j][k]

Łatwo zauważyć, że przy obliczaniu DP[i][j][k] będziemy się odwoływać tylko do elementów, które zostały wcześniej obliczone.

Złożoność O(n*m).