v 0. Pasted by slipstak2 as cpp at 2011-10-25 19:47:01 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Олимпиадные задачи
  3. // Задача A. Движение по полосам
  4. // ibelyaev: 25Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23. // m - количество дорог
  24. // n - количество полос
  25. int n,m;
  26. vector<vector<long long> > mem;
  27.  
  28.  
  29. // s - количество использованных полос
  30. // r - количество дорог
  31. long long dp(int s, int r) {
  32.  
  33.     if (s == 1) return 1;
  34.     if (mem[s][r] != -1)
  35.         return mem[s][r];
  36.  
  37.     long long res = dp(s-1,r);
  38.     for (int i = 1; i < r; ++i)
  39.         res += 2*dp(s - 1, r - i);
  40.     return mem[s][r] = res;
  41. }
  42. int main()
  43. {
  44.     freopen("input.txt","r",stdin);
  45.     freopen("output.txt","w",stdout);
  46.  
  47.     scanf("%d %d", &m, &n);
  48.     mem.resize(n+1,vector<long long>(m+1,-1));
  49.     printf("%lld", dp(n,m));
  50.  
  51.     return 0;
  52. }


Editing is locked.