|
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 |