v 0. Pasted by slipstak2 as cpp at 2011-01-06 17:26:41 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 12.
  2. // 12E. Водопровод [wpipe]
  3. // Нерекурсивный перебор с использованием ДП
  4. // ibelyaev: 05Jan2011
  5.  
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <vector>
  9. using namespace std;
  10.  
  11. const int MAX_LEN = 4*1000*10+2;
  12. const int MAX_VALUE = 1e9;
  13. const int OSN = 11;
  14.  
  15. int k;
  16. vector<int> C,L,step;
  17. int x1,y1,x2,y2;
  18. int minAmount = MAX_VALUE;
  19. void input()
  20. {
  21.     cin>>x1>>y1>>x2>>y2>>k;
  22.     C.resize(k);
  23.     L.resize(k);
  24.     step.resize(k);
  25.     for (int i=0;i<k;i++)
  26.         cin>>L[i];
  27.     for (int i=0;i<k;i++)
  28.         cin>>C[i];
  29. }
  30. int _abs(int a)
  31. {
  32.     return (a<0)?-a:a;
  33. }
  34. void UnPack(int num, int mas[])
  35. {
  36.     int pos = 0;
  37.     while (pos!=k)
  38.     {
  39.         mas[pos++] = num % OSN;
  40.         num /= OSN;
  41.     }   
  42. }
  43. void solve()
  44. {
  45.     step[0] = 1;
  46.     for (int i=1;i<k;i++)
  47.         step[i] = step[i-1] * OSN;
  48.  
  49.     vector<vector<int> > dp(MAX_LEN * 2);
  50.     dp[MAX_LEN].push_back(0);
  51.     for (int i=0;i<k;i++)
  52.     {
  53.         vector<vector<int> > ndp(dp);
  54.         for (int j=0;j<dp.size();j++)
  55.         {
  56.             for (int p=0; p<dp[j].size(); p++)
  57.             {
  58.                 for (int mul = 1; mul <= C[i]; mul++)
  59.                 {
  60.                     int nextState = dp[j][p] + mul * step[i];
  61.  
  62.                     int nextLen = j + mul * L[i];
  63.                     ndp[nextLen].push_back(nextState); 
  64.  
  65.                     nextLen = j - mul*L[i];
  66.                     ndp[nextLen].push_back(nextState);
  67.                 }
  68.             }
  69.         }
  70.         dp.swap(ndp);
  71.     }
  72.     vector<int> x = dp[MAX_LEN + _abs(x1-x2)];
  73.     vector<int> y = dp[MAX_LEN + _abs(y1-y2)];
  74.  
  75.     int stateX[4], stateY[4];
  76.     for (int i=0;i<x.size();i++) {
  77.         UnPack(x[i],stateX);
  78.         for (int j=0;j<y.size();j++) {
  79.             UnPack(y[j],stateY);
  80.             bool isOK = true;
  81.             int curAmount = 0;
  82.             for (int p = 0; p < k; p++)
  83.             {
  84.                 curAmount += stateX[p] + stateY[p];
  85.                 if (stateX[p] + stateY[p] > C[p]) {
  86.                     isOK = false;
  87.                     break;
  88.                 }
  89.             }
  90.             if (isOK)
  91.                 minAmount = min(minAmount, curAmount);
  92.         }
  93.     }
  94.     if (minAmount == MAX_VALUE)
  95.         cout<< -1;
  96.     else
  97.         cout<<minAmount;
  98. }
  99. int main()
  100. {
  101.     freopen("input.txt","r",stdin);
  102.     freopen("output.txt","w",stdout);
  103.  
  104.     input();
  105.     solve();
  106.     return 0;
  107. }


Editing is locked.