Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare solutie pentru problema: tv

Titlul problemei tv
Grupa Grupa B
Problema numarul 2
Runda numarul 16
Solutie oficiala #include

#define oo -30000
#define MAX 10
#define abonat(A) ((A) >= n-m ? 1 : 0)

int n,m, rez;
short total[MAX][MAX],temp[MAX][MAX],vecin[MAX][MAX],cost[MAX][MAX];
short grad[MAX],suma[MAX];

void citeste(void);
int dfs(int);
void afisare(void);

int main(void)
{citeste();
dfs(0);
rez = m;
while (total[0][rez] < 0) rez--;
afisare();
return 0; }

void afisare(void)
{FILE *f;
f=fopen("tv.out","wt");
fprintf(f,"%d\n",rez);
fclose(f); }

int max(int a, int b, int c)
{ if (a >= b && a >= c) return a;
if (b >= a && b >= c) return b;
return c; }

int dfs(int vf)
{ int i, j, k, nr, nnr, vfnou;
for (i=1; i<=m; i++)
total[vf][i] = temp[vf][i] = oo;
total[vf][0] = 0;
nr = 0;
for (i=0;i {
vfnou = vecin[vf][i];
temp[vf][0] = 0;
if (abonat(vfnou))
{nr++;
for (j=1;j<=nr;j++)
temp[vf][j] = max(total[vf][j], temp[vf][j], total[vf][j-1] - cost[vf][i] + suma[vfnou]);
}
else
{nnr = dfs(vfnou);
nr += nnr;
for (j=1;j<=nr;j++)
for (k=1;k<=nnr && j-k>=0;k++)
temp[vf][j] = max(total[vf][j], temp[vf][j], total[vf][j-k] - cost[vf][i] + total[vfnou][k]);
}

for (j=0;j<=nr;j++)
{total[vf][j] = temp[vf][j];
temp[vf][j] = oo;
}
}

return nr;
}

void citeste(void)
{
FILE *f;
int i,j;
f=fopen("tv.in","rt");
fscanf(f,"%d %d",&n,&m);
for (i=0;i {
fscanf(f,"%d",&grad[i]);
for (j=0;j {
fscanf(f,"%d %d",&vecin[i][j],&cost[i][j]);
vecin[i][j]--;
}
}
for (i=n-m;i {
grad[i] = 0;
fscanf(f,"%d",&suma[i]);
}
fclose(f);
}

Explicatii despre modul de punctare 7 teste (primele 5 teste 6 puncte, ultimele doua 10 puncte)

Download arhiva teste de intrare  

Click aici pentru a va intoarce

© 2002 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com