Paste will expire never.
- // Меньшиков. Тренировка 12.
- // 12E. Водопровод [wpipe]
- // Нерекурсивный перебор с использованием ДП
- // ibelyaev: 05Jan2011
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- const int MAX_LEN = 4*1000*10+2;
- const int MAX_VALUE = 1e9;
- const int OSN = 11;
- int k;
- vector<int> C,L,step;
- int x1,y1,x2,y2;
- int minAmount = MAX_VALUE;
- void input()
- {
- cin>>x1>>y1>>x2>>y2>>k;
- C.resize(k);
- L.resize(k);
- step.resize(k);
- for (int i=0;i<k;i++)
- cin>>L[i];
- for (int i=0;i<k;i++)
- cin>>C[i];
- }
- int _abs(int a)
- {
- return (a<0)?-a:a;
- }
- void UnPack(int num, int mas[])
- {
- int pos = 0;
- while (pos!=k)
- {
- mas[pos++] = num % OSN;
- num /= OSN;
- }
- }
- void solve()
- {
- step[0] = 1;
- for (int i=1;i<k;i++)
- step[i] = step[i-1] * OSN;
- vector<vector<int> > dp(MAX_LEN * 2);
- dp[MAX_LEN].push_back(0);
- for (int i=0;i<k;i++)
- {
- vector<vector<int> > ndp(dp);
- for (int j=0;j<dp.size();j++)
- {
- for (int p=0; p<dp[j].size(); p++)
- {
- for (int mul = 1; mul <= C[i]; mul++)
- {
- int nextState = dp[j][p] + mul * step[i];
- int nextLen = j + mul * L[i];
- ndp[nextLen].push_back(nextState);
- nextLen = j - mul*L[i];
- ndp[nextLen].push_back(nextState);
- }
- }
- }
- dp.swap(ndp);
- }
- vector<int> x = dp[MAX_LEN + _abs(x1-x2)];
- vector<int> y = dp[MAX_LEN + _abs(y1-y2)];
- int stateX[4], stateY[4];
- for (int i=0;i<x.size();i++) {
- UnPack(x[i],stateX);
- for (int j=0;j<y.size();j++) {
- UnPack(y[j],stateY);
- bool isOK = true;
- int curAmount = 0;
- for (int p = 0; p < k; p++)
- {
- curAmount += stateX[p] + stateY[p];
- if (stateX[p] + stateY[p] > C[p]) {
- isOK = false;
- break;
- }
- }
- if (isOK)
- minAmount = min(minAmount, curAmount);
- }
- }
- 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;
- }
Editing is locked.