Programare dinamica in O(3^n)

[•balakraz94]

   Am si eu o intrebare. Cum se rezolva problemele de dinamica in 3^n? Trebuie sa imi implementez eu operatiile pentru baza 3  sau le pot folosi cumva pe cele deja existente in C++ pentru baza 2.

   Pana acum nu am gasit nici o rezolvare care sa implementeze un algoritm in 3^n, asa ca nu prea stiu cum sa fac.

   Daca cineva stie vreun tutorial sau are vreo sursa cu o rezolvare de dinamica in 3^n, il rog sa posteze.

Multumesc,
Razvan

[•S7012MY]

Tu vrei sa calculezi ceva pentru o multime. Pentru asta tu o imparti in 2 submultimi disjuncte. Gasesti o explicatie foarte buna la problema scara2.
O aplicatie foarte buna este problema efect: http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1353

Cod:

#include <cstdio>
#define DN 17
#define inf -2147483647
#define deb(n) fprintf(stderr,"%d ",(n));
#define debnl fprintf(stderr,"\n");

//E(M1)*E(M2)-2*E(M1)-2*E(M2)-6

int n,v[DN],lm,sl[1<<DN];

inline int max(int a, int b) {
    if(a>b) return a;
    return b;
}

int main()
{
    freopen("efect.in","r",stdin);
    freopen("efect.out","w",stdout);
    scanf("%d",&n);
    lm=(1<<n)-1;
    for(int i=0; i<=lm; ++i) sl[i]=inf;
    for(int i=0; i<n; ++i) {
        scanf("%d",&v[i]);
        sl[1<<i]=v[i];
    }
    for(int s=1; s<=lm; ++s)
        for(int i=s&(s-1);i>0;i=s&(i-1))
            sl[s]=max(sl[s],1LL*sl[i]*sl[i^s]-2LL*sl[i]-2LL*sl[i^s]-6LL);
    printf("%d\n",sl[lm]);
    return 0;
}

Mai gasesti pe infoarena:
zebughil
colorare
scara2