Curs 5.

DEFINITIE +RASPUNS:
Raspuns: cout << D[1][n]
long long 
D[i][j] = numar => 101 => (1,3)

D[2][2] = {2}
D[2][3] = {2}
4 4 
D[2][3] = {2,3}

D[i][j][X]= 1 daca se poate realiza numarul X pietre la finalul intervalului X = 0 la 20


RECURENTA:
D[i][j] = poate sa plece orice k din intervalul (i,j)
            (i,k-1) si k-1 se va intelege cu k
            (k+1,n) si se va intelege k+1 cu k
           k = split point 


Intializare:
for(int i = 1; i <= n; ++i)
  D[i][i][a[i]]=1;
for(int lung = 2; lung <= n; ++lung)   
  for(int i = 1; i <= n-lung+1; ++i) {
    j =i+lung-1;
     for(ksplit = i; ksplit <= j; ++ksplit)
       for(int primval = 0; primval <= 20; ++primval)
         for(int doival= 0; doival <= 20; ++doival)
           if(d[i][k][primval] === 1 && d[i][k+1][doival] === 1)
                 dp[i][j][abs(primval-doival)] = 1;
       
  }
  
  
  i                     j
  i        k  k+1   j
  
 primval  doival
  for(int i = 0; i<=20; ++i)
    if(d[1][n][i] == 1)
      cout<<i <<" ";
      
      
      d[i][j] = (i,j) , se folosesc la stergeri de obicei
    d[i][j] = i+1,j si i,j-1 dar obligatoriu trebuie specificat in problema ca pleaca capetele (mai simple)
    d[i][j] = (i,k) (k+1,j) k split point ( se poate sterge orice numar din interval)
                  a      b 
  

D[i][j] = 1, daca pot sa sterg secventa folosind palindroame de lungime 3
          =0, daca nu pot ......
        
        
Raspuns:
D[1][n];

Intializare:
D[i][j] = 0;

D[i][i+2]= 1 daca s[i] == s[i+2]


(i,i+2)
s[i] s[i+1] s[i+2]
const int NMAX = 

aaa|bbb
123456
miaham
d[3][5] = 1
d[1][6] = 1
d[1][6] = d[1][3] & d[4][6]
void dynamic(char s[]) {
  dp[i][j] = 0;
  for(int i = 1; i <= n-2; ++i)
   if(s[i] == s[i+2])
    D[i][i+2]= 1
   for(int lung = 4; lung <= n; ++lung)   
      for(int i = 1; i <= n-lung+1; ++i) {
        j =i+lung-1;
        for(int k = i; k <= j; ++k)
          if(d[i][k] == 1 && d[k+1][n] == 1)
              d[i][j] = 1;
         if(!d[i][j] && s[i] == s[j]) { 
           //i in interior
           for(int k = i+1; k <= j-1; ++k)
             if(dp[i+1][k-1] == 1 && dp[k+1][j-1] == 1)
                 dp[i][j] = 1;
             //caz1
             if(dp[i+2][j-1] == 1)
                 dp[i][j] = 1;
           if(dp[i+1][j-2] ==1)
             dp[i][j] = 1;
         }
                    i                       j
          caz1 mixxxxxxxxxxxm
          mxxxxxxxxim
          caz 3 mxxxxixxxxxm
        }
}
cin >> t;
for(int i = 1;i <=t;++i) {
 char s[NMAX];
  cin >> s;
  dynamic(s);
}

cin >> n >> m;
//n-noduri
//m -moduri
Reprezentari in memorie
Cazul 1. Matrice de adiacenta:

 i - j  => a[i][j] = 1 si a[j][i] = 1;
 i -> j => a[i][j] = 1;
 
 O(N*M)
 Cazul 2. Liste de adiacenta:
 vector<int> g[NMAX];
 
 cin >>i >> j;
 
 g[i].push_back(j)
 g[j].push_back(i);
 
 Memorie: O(N+M) 
 
 Cazul 3. Liste de muchii
 
 pair<int,int> Muchii[MMAX];
 for(int i = 1; i <= m; ++i)
   cin >> muchii[i].first>>muchii[i].second;
   
   1. Dijkstra
     start;
     D[i] = distanta pana la nodul i de la nodul start;
 Grafuri cu costuri:
 
    #include <priority_queue>
    using namespace std;
    const int NMAX = 100.000;
    priority_queue<pair<int,int>Q:
    vector<pair<int,int>G[NMAX];
    
    int main() 
    { 
      cin >> n >> m;
      for(int i = 1; i <=m; ++i) {
        cin >> x >> y >> cost;
        g[x].push_back({y,cost});
        g[y].push_back({x,cost});
        
      }
      cin >> nodstart;
      q.push({0,nodstart});
      while(!q.empty()){ 
        int {distanta,nod} = q.top();
        q.pop();
        if(distanta != d[nod])
          continue;
        for(auto vecin : g[nod]) {
          {y,cost} = vecin;
          if(d[y] > d[nod] + cost) {
            d[y] = d[nod] + cost;
            q.push({d[y],y});
          }
        }
      }
    }
    M <= N
    
    N + M*log2M
    M = numarul de muchii
    N = numarul de noduri
    Muchii = (n-1)*(m-1)
    N*M = numarul de noduri
    
    N*M + N*M * log2 ( N*M)
    
    N*M
    
    
 

lg(a*b) = lg(a) + lg(b);

 int d[NMAX];
 int nr_solutii[NMAX];
 cin >> n >> m;
      for(int i = 1; i <=m; ++i) {
        cin >> x >> y >> cost;
        g[x].push_back({y,cost});
        g[y].push_back({x,cost});
        
      }
      
      nodstart = 1;
      q.push({0,nodstart});
      while(!q.empty()){ 
        int {distanta,nod} = q.top();
        q.pop();
        if(distanta != d[nod])
          continue;
        for(auto vecin : g[nod]) {
          {y,cost} = vecin;
          if(d[y] > d[nod] + cost) {
            d[y] = d[nod] + cost;
            nr_solutii[y] = nr_solutii[nod];
            q.push({d[y],y});
          }
          else
           if(d[y] == d[nod] + cost) {
            nr_solutii[y] += nr_solutii[nod];

          }
        }
      }
      
      cout<<d[i];
      numarul de drumuri cu distanta pana in i
      
    }

2
3 5 => 0 2 1

a 1 8 + 0
b 2 8 + 1
c 3 8 + 2

3*X + a
3*X + b
3*X + c
11 = 
3*1 + a

3*4 + c
 12 
 
 mij ....mij + min_sir
 
 
 0 
     
 0 ---5--> 2
 0---3-->0
 
 cost[rest] = 
 cost[0] = a[1];
 Resturile la impartirea cu minimul din sir
 
 3
 0 1 2
 3
 q.push{3,0}
 while(!q.empty() {
   nod = q.top().second;
   
   for(int i=1; i < a[0]; ++i) {
     nr = (nod +i )%nod;
     if(d[nr] > d[nod] + cost[i])
     { ...
     }
   }
 }
 
 Raspuns:
 
 max(D[nod]) - (a[1] - 1)
 
 0 = 3
 2 5
 1: 10
 
 
 =>10 => 10 - (a[1] -1)
 
  2   0    1
  8   9 10