ciao a tutti, sto provando a risolvere Sequence of Balls utilizzando l’algoritmo di Levenshtein ma non riesco a superare i 58 punti, potreste indicarmi dove sbaglio?
#include < iostream>
using namespace std;
int minimo(int x, int y, int z){
return min(min(x,y),z);
}
Ciao, stando alle specifiche 2*CostoSwap>=CostoInserimento+CostoCancellazione questa configurazione non dovrebbe verificarsi … o sbaglio?
Ho utilizzato il link che mi hai girato tu per determinare l’algoritmo, dovrei utilizzare la variante Distance with adjacent transpositions?
Ho provato con questo (vedi le righe con il commento ///CONTROLLO AGGIUNTO), mi risolve il caso in questione ma salta comunque in test della piattaforma
int d[4002][4002];
int adiacenze[26];
int calcolaDistanza(string a, string target, int cIns, int cCanc, int cRim, int cSwap) {
///calcolo il costo nel caso in cui una delle due lettere risultasse vuota
if (a.length() == 0) {
return target.length() * cIns;
}
if (target.length() == 0) {
return a.length() * cCanc;
}
///nel caso in cui le prime due lettere risultassero differenti calcolo il costo minimo
///per farle divenire uguali ossia: il rimpiazzo o la cancallazione con inserimento
if (a[0]!= target[0]) {
d[0][0] = min(cRim, cCanc + cIns);
if(a[0]==target[1]&&a[1]==target[0]) ///CONTROLLO AGGIUNTO
d[0][0] = min(d[0][0], cSwap);
}
///VALORIZZO la prima riga della matrice
for (int i = 1; i < a.length(); i++) {
int deleteDistance = d[i - 1][0] + cCanc; ///costo precedente + cancellazione ultima lettera
int insertDistance = (i +1 ) * cCanc + cIns; ///inserisco la corrente e le cancello tutte
int matchDistance = i * cCanc + (a[i] == target[0] ? 0 : cRim); ///cancello tutte le precedenti ed eseguo una sostituzione
d[i][0] = min(min(deleteDistance, insertDistance),matchDistance);
}
///VALORIZZO la prima colonna della matrice
for (int j = 1; j < target.length(); j++) {
int deleteDistance = (j + 1) * cIns + cCanc; ///inserisco tutte le lettere fino alla corrente e poi cancello l'ultima
int insertDistance = d[0][j - 1] + cIns; ///costo precedente + inserimento ultima lettera
int matchDistance = j * cIns + (a[0] == target[j] ? 0 : cRim); ///inserisco tutte le precedenti ed eseguo una sostituzione con l'ultima
d[0][j] = min(min(deleteDistance, insertDistance),matchDistance);
}
adiacenze[((int)a[0])-97]=0;
for (int i = 1; i < a.length(); i++) {
///verifico se la lettera corrente di A corrisponde alla prima lettera di B
int maxSourceLetterMatchIndex = (a[i] == target[0] ? 0: -1);
for (int j = 1; j < target.length(); j++) {
int candidateSwapIndex = adiacenze[((int)target[j])-97];
int jSwap = maxSourceLetterMatchIndex;
int deleteDistance = d[i - 1][j] + cCanc;
int insertDistance = d[i][j - 1] + cIns;
int matchDistance = d[i - 1][j - 1];
if (a[i] != target[j]) {
matchDistance+=cRim;
} else {
maxSourceLetterMatchIndex = j;
}
int swapDistance;
if (candidateSwapIndex != 0 && jSwap != -1) {
int iSwap = candidateSwapIndex;
int preSwapCost=0;
if (iSwap == 0 && jSwap == 0) {
preSwapCost = 0;
} else {
preSwapCost = d[max(0, iSwap - 1)][max(0, jSwap - 1)];
}
swapDistance = preSwapCost + (i - iSwap - 1) * cCanc + (j - jSwap - 1) * cIns + cSwap;
}else {
swapDistance = 999999;
}
///CONTROLLO AGGIUNTO
if (i>=1 && j>=1 && a[i-1] == target[j] && a[i] == target[j-1]){
if(i-1!=0 && j-1!=0){
swapDistance= d[i-2][j-2]+cSwap;
}else{
swapDistance= d[i-1][j-1];
}
d[i][j] = min(min(min(deleteDistance, insertDistance), matchDistance), swapDistance);
}else{
d[i][j] = min(min(min(deleteDistance, insertDistance), matchDistance), swapDistance);
}
}
adiacenze[((int)a[i])-97]=i;
}
return d[a.length() - 1][target.length() - 1];
}
int main(){
int costoInserimento,costoCancellazione,costoRimpiazzo,costoScambio;
int i,j,N,M;
string NA;
string NB;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>costoInserimento>>costoCancellazione>>costoRimpiazzo>>costoScambio;
cin>>NA>>NB;
N=NA.size();
M=NB.size();
cout<<calcolaDistanza(NA,NB,costoInserimento,costoCancellazione,costoRimpiazzo,costoScambio)<<endl;
}
