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


Балканска олимпиада по информатика 2005, Задача 2.1. SAILING RACE

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

Решение

Ключовото наблюдение в тази задача е , че обходените знаци във всеки момент представляват интервал, който включва знаците от обходения с най-малък номер до обходения с най-голям номер. Това е така, защото ако една лодка е посетила знак sи знак t, като s<=t, то тя е минала и през знаците между тях.

За решението на задачата може да се използва динамично оптимиране. Нека е дефинирана функция F(p,q), която за интервала [min(p,q), max(p,q)] връща минималната сума от общи разстояния при обхдождането му, като последният посетен знак е този с номер p. Нека знакът с координата 0 е с номер kв сортираната по координати последователност от знаци. Тогава
F(k, k) = 0.

Във всеки един момент интервалът, който е обходен от една лодка включва в себеси знака с координата 0. Ето защо на стойностите F(p,q), за които kне е от интервала [min(p,q), max(p,q)] следва да се присвои безкрайно голяма стойност, тъй като те не са постижими. Останалите стойности на Fмогат да се сметнат по следната формула:

Ако p<q
F(p,q) = min[ F(p+1,q) + (K(p+1) – K(p))*(n-(p-q+1)), F(q,p+1) + (K(q) – K(p))*(n-(p-q+1)) ]
F(q,p) = min[ F(p,q-1) + (K(q) – K(p))*(n-(p-q+1)), F(q-1,p) + (K(q) – K(q-1))*(n-(p-q+1)) ]

където K(x)е координатата на знака с номер x, a n е броят на знаците по трасето, като броим и този с координата 0.

Отговорът на задачата е по-малката от двете стойности F(1,n) и F(n,1).

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


#include <stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define INF 1000000000
#define MAXN 202

 // an array for computing the values
 int b[MAXN][MAXN];
 // an array with the coordinates
 int a[MAXN];
 int n;
 FILE *f1,*f2;

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

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

  for (i=1;i<=n;i++)
   fscanf(f1,"%d",&a[i]);

  for (k=1;k<=n;k++)
   if (a[k]>0)
    break;

  n++;

  for (j=n;j>k;j--)
   a[j]=a[j-1];

  a[k]=0;

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

  b[k][k]=0;

  for (i=1;i<n;i++)
   for (j=1;j<=n-i;j++)
    {
     b[j][j+i]=min(b[j+1][j+i]+(a[j+1]-a[j])*(n-i)
		,b[j+i][j+1]+(a[j+i]-a[j])*(n-i));
     b[j+i][j]=min(b[j][j+i-1]+(a[j+i]-a[j])*(n-i)
		,b[j+i-1][j]+(a[j+i]-a[j+i-1])*(n-i));
    }

  fprintf(f2,"%d\n",min(b[1][n],b[n][1]));

  return 0;
 }



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


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