Решение задачи "Водопровод" с Меньшиков

Без пояснения   Просмотров: 14


Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x1, y1), а вторая - в точке (x2, y2).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L1, L2, ..., LK и количество отрезков каждой длины C1, C2, ..., CK, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 <= K <= 4, 1 <= x1, y1, x2, y2, Li <= 1000, 1 <= Ci <= 10, все числа целые.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
const int MAX_VALUE = 1e9;
int k;
vector<int> C,L;
int x0, y0, x1, y1;
int dx, dy;
void input()
{
    cin>>x0>>y0>>x1>>y1>>k;
    C.resize(k);
    L.resize(k);
    for (int i=0;i<k;i++)
        cin>>L[i];
    for (int j=0;j<k;j++)
        cin>>C[j];
}
int _abs(int a)
{
    return (a<0) ? -a:a;
}
int minAmount = MAX_VALUE;
int curAmount;
bool isLast = false;
void rec(int pos, int curLen, int totalLen)
{
    if ((totalLen - curLen) % L[pos] == 0)
    {
        int lastAmount = _abs(totalLen - curLen) / L[pos];
        if (lastAmount <= C[pos])
        {
            if (isLast)
                minAmount = min(minAmount, curAmount + lastAmount);
            else
            {
                isLast = true;
                curAmount += lastAmount;
                C[pos] -= lastAmount;
 
                rec(0,0,dy);
 
                C[pos] += lastAmount;
                curAmount -= lastAmount;
                isLast = false;
            }
        }
    }
    if (pos == k-1)
        return;
    for (int x = -C[pos]; x <= C[pos]; x++)
    {
        C[pos]-= _abs(x);
        curAmount += _abs(x);
 
        rec(pos+1, curLen + x * L[pos], totalLen);
 
        curAmount -= _abs(x);
        C[pos] += _abs(x);
    }
}
 
void solve()
{
    dx = _abs(x0 - x1);
    dy = _abs(y0 - y1);
    // a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx
    rec(0,0,dx);
    if (minAmount == MAX_VALUE)
        cout<<-1;
    else
        cout<<minAmount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться