Cod sursa(job #946873)

Utilizator enedumitruene dumitru enedumitru Data 6 mai 2013 08:11:07
Problema Distante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
using namespace std;
ifstream f("dist.in");
ofstream g("dist.out");
char a[502], b[502];
void citire()
{   f.getline(a,502,'\n');
    f.getline(b,502,'\n');
}
void solve()
{
        g<<a<<'\n';
        g<<b<<'\n';
}
int main()
{   citire();
    solve();
    return 0;
}
/*
1.	Vom extrage cuvintele din prima propoziţie şi le vom reţine într-un vector.
2.	Vom elimina spaţiile din cea de a doua propoziţie obţinând astfel un şir de litere (s).
Problema se reduce la a insera spaţii în acest şir de litere astfel încât dist(P1,P2) să fie minimă. Deoarece trebuie să determinăm şi numărul minim de operaţii necesare, vom reţine şi lungimea fiecărui cuvânt din cea de a doua propoziţie (în forma iniţială), precum şi în forma modificată.
Problema se rezolvă prin programare dinamică.
Subproblemă:
Să se determine distanţa minimă dintre propoziţia formată din cuvintele i, i+1, ... din prima propoziţie şi
 propoziţia care se poate obţine din caracterele j, j+1, ... din cea de a doua propoziţie (o vom nota dist[i][j]).
dist[i][j] este cea mai mică valoare care se poate obţine considerând că vom forma cuvântul curent din cea de a doua propoziţie
 din k litere din s (sjsj+1...sj+k-1) (1≤k<20, cu condiţia să mai existe k de litere în s),
 adică este distanţa dintre cuvântul i din prima propoziţie şi cuvântul sjsj+1...sj+k-1, la care se adaugă dist(i+1, j+k).
Vom nota cu nrmin[i][j]=numărul minim de operaţii necesare pentru a obţine dist[i][j].
nrmin[i][j]=este numărul de operaţii necesare pentru a forma al i-lea cuvânt din cea de a doua propoziţie
 din literele j, j+1, ..., j+kmin-1 la care se adauga nrmin[i+1][j+kmin], unde kmin este acel k pentru care se obţine pentru dist[i][j] valoarea minimă.
*/