Отримання знань

дистанційна підтримка освіти школярів


Транспортировка
http://acm.pku.edu.cn/JudgeOnline/problem?id=1040

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

int n; /* capacity */
int m; /* number of stations */
int count; /* number of orders */

struct order
{
int from; /* from station */
int to; /* to station */
int passangers; /* no of passangers */
int price; /* price */
int remaining; /* sum of prices of this and all remainings orders in the sequence */
}
orders[32];

int train[16];

int best;

void try_it(
int start, /* index of order to start with */
int earnings) /* price of already allocated orders */
{
if(earnings > best)
best = earnings;
for( ; start < count; start++)
{
int i;
if(earnings + orders[start].remaining < best)
return;
for(i = orders[start].from; i < orders[start].to; i++)
{
if((train[i] += orders[start].passangers) > n)
goto skip;
}
try_it(start + 1, earnings + orders[start].price);
i--;
skip:
for( ; i >= orders[start].from; i--)
train[i] -= orders[start].passangers;
}
}

int price_cmp(const void *a, const void *b)
{
return ((struct order *)b) -> price - ((struct order *)a) -> price;
}

int main(void)
{
int i, s;
for(;;)
{
scanf("%d%d%d", &n, &m, &count);
if(!n && !m && !count) break;
for(i = 0; i < count; i++)
{
scanf("%d%d%d", &orders[i].from, &orders[i].to, &orders[i].passangers);
orders[i].price = (orders[i].to - orders[i].from) * orders[i].passangers;
}
qsort(orders, count, sizeof(orders[0]), price_cmp);
for(s = 0, i = count - 1; i >= 0; i--)
orders[i].remaining = (s += orders[i].price);
memset(train, 0, sizeof(train[0]) * (m + 1));
best = 0;
try_it(0, 0);
printf("%d\n", best);
}
return 0;
}
 
Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)