Текущ брой на Списание ИнфоМан
 


Балканска олимпиада по информатика 2005, Задача 2.2. TICKETS

Уловието на задачата може да прочетете тук.

Решение

За да се пресметне закъснението за дадена група от страници се използва следната формула:

(A[1]+A[2]+…+A[k])*k/2, като A[i] е популярността на дадената страница.

За да се намери отговора на задачата може да се използва динамично оптимиране. Нека е дефинирана функция F(n,k), която дава средното закъснение при оптималното разпределение на първите n страници сред първите k канала.

За стойността F(0,0) е очевидно, че е 0. Останалите стойности на Fмогат да се пресметнат по следната формула:

F(p,q) = min(F(k-1,q-1) + (A[k]+A[k+1]+…+A[p])*(p-k+1)/2), като kприема стойности в интервала [q,p].

Идеята на тази формула е за фиксирани брой страници и канали, последните няколко страници да се поставят в последния канал и да се избере най-доброто от всички такива разположения. За да се намери начинът, по който са разпределени страниците по канали, е нужно да се пази как е получена всяка стойност.

Оптималното разпределние на страниците по канали се съдържа в F(L,D), като L e броят на страниците, а е броят на каналите.

Примерна реализация


#include <stdio.h>

 // an array for computing the values
 long double b[302][22];
 // an array to find how we received the best solution
 int prev[302][22];
 long double s[302];
 // an array for keeping the popularity of the pages
 long double a[302];
 int n,m;
 FILE *f1,*f2;

 void show (int i,int j)
 {
  if (j==0)
   return;
  show(prev[i][j]-1,j-1);
  fprintf(f2,"%d\n",i);
 }

 int main ()
 {
  int i,j,k;
  f1=fopen("tickets.in","r");
  f2=fopen("tickets.out","w");

  fscanf(f1,"%d%d",&m,&n);

  for (i=1;i<=n;i++)
   {
    fscanf(f1,"%llf",&a[i]);
    s[i]=s[i-1]+a[i];
   }

  for (i=0;i<=n;i++)
   for (j=0;j<=n;j++)
    b[i][j]=1e12;

  b[0][0]=0;

  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    for (k=j;k<=i;k++)
     if (b[i][j]>b[k-1][j-1]+((s[i]-s[k-1])*(i-k+1))/2.0)
      {
       b[i][j]=b[k-1][j-1]+((s[i]-s[k-1])*(i-k+1))/2.0;
       prev[i][j]=k;
      }

   show(n,m);

   return 0;
 }


Автор: Ростислав Руменов


обратно към брой 27