Балканска олимпиада по информатика 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 броят на страниците, а D е броят на каналите.
Примерна реализация
#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
|