Балканска олимпиада по информатика 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
|