Moze mala pomoc oko ovog zadatka?
Jedan DFS obilazak.
Imas 2 promenljive - lo i hi, gde je lo maksimalan broj koji se moze dobiti tako da je lo <= trazenog, hi minimalan tako da hi >= trazenog.
Neka je dp[i] broj nacina na koji mozes dobiti broj i na putu od korena do cvora u kojem si trenutno (x).
for(int i = s; i >= 0; i–)
{
int j = i + a[x];
if(!d[i]) continue;
if(j > s) hi = min(hi, j);
else if(j <= s)
{
lo = max(lo, j);
d[j] += d[i];
}
}
E sad rekurzivno pozoves za sinove, ali ne smes zaboraviti da se “vratis” i da posle ispitivanja puta od cvora i do nekog lista obrises ono sto si dodavao u dp niz (ometace ostatak procesa, tj. put od cvora i pa do nekog drugog lista).
for(int i = a[x]; i <= s; i++)
{
int j = i - a[x];
if(!d[j]) continue;
d[i] -= d[j];
}
Ovo resenje mi radi za prva 4 test primera ali daje MLE na ostalima, sto ne znaci da je zaista MLE (Problem sa zad Porodicno stablo (Državno 2014 SŠ - A2))
Proverio sam da li zapravo postoji problem sa memorijom tako sto sam submitovao neki od kodova koji je prolazio na takmicenju i na moje iznenadjenje prosao je bez problema.
Kako? Kada ucitavam input sa samo 4 varijable dobijem MLE? Uostalom, jel mozes postaviti taj kod?
#include <cstdio>
#include <algorithm>
using namespace std;
short son[10005];
short ep[10005],ek[10005];
short dif[10005];
int n,s;
int val[10005];
char notrut[10005];
inline bool komp(int a,int b)
{
return dif[a]<dif[b];
}
inline void setdif(int u)
{
for (int i=ep[u]; i<ek[u]; i++)
setdif(son[i]);
sort(son+ep[u],son+ek[u],komp);
if (ep[u]==ek[u])
{
dif[u]=1;
return;
}
if (ep[u]+1==ek[u])
{
dif[u]=dif[son[ep[u]]];
return;
}
dif[u]=max(dif[son[ek[u]-1]],(short)(dif[son[ek[u]-2]]+1));
}
int nodes[40][315];
int cnode;
int best;
inline int aps(int a)
{
if (a<0)
return -a;
return a;
}
inline void uporedi(int val)
{
if (aps(s-best)>aps(s-val) || (aps(s-best)==aps(s-val) && val<best))
best=val;
}
inline void skinicvor()
{
for (int i=0; i<315; i++)
nodes[cnode-1][i]=nodes[cnode][i];
cnode--;
}
inline void napravicvor(int val)
{
for (int i=0; i<315; i++)
nodes[cnode+1][i]=nodes[cnode][i];
cnode++;
for (int i=s-1; i>=0; i--)
if (nodes[cnode][i>>5]&(1<<(i&31)))
{
uporedi(i+val);
if (i+val<=s)
nodes[cnode][i+val>>5]|=1<<(i+val&31);
}
}
inline void resi(int u)
{
char del=0;
while (ep[u]<ek[u])
{
int v=son[ep[u]];
napravicvor(val[v]);
ep[u]++;
if (ep[u]==ek[u])
{
del=1;
skinicvor();
}
resi(v);
}
if (del==0)
cnode--;
}
int main()
{
scanf("%d%d",&n,&s);
int cdg=1;
for (int i=1; i<=n; i++)
{
scanf("%d",&val[i]);
int deg;
scanf("%d",°);
ep[i]=cdg;
ek[i]=ep[i]+deg;
cdg+=deg;
for (int j=ep[i]; j<ek[i]; j++)
{
scanf("%d",&son[j]);
notrut[son[j]]=1;
}
}
int rut=-1;
for (int i=1; i<=n; i++)
if (notrut[i]==0)
rut=i;
setdif(rut);
cnode=1;
nodes[1][0]=1;
napravicvor(val[rut]);
resi(rut);
printf("%d\n",best);
}
Evo ga kod.U prva dva reda treba ukljuciti biblioteke cstdio i algorithm ali se ne vide dobro.
Zaista nema problema sa memorijom, prosao je sada i moj kod sa sledecim izmenama:
Umesto <bits/stdc++.h> sam stavio cstdio i algorithm, i umesto void dfs(int x) - inline void dfs(int x)
Memorijsko ogranicenje za taj zadatak je previse nisko, treba da bude vise. Moguce je da dosta tacnih resenja ne prolazi.
Izgleda da je to ogranicenje ispravno