Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Олимпиадные задачи
- // Задача A. Движение по полосам
- // ibelyaev: 25Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.html
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- // m - количество дорог
- // n - количество полос
- int n,m;
- vector<vector<long long> > mem;
- // s - количество использованных полос
- // r - количество дорог
- long long dp(int s, int r) {
- if (s == 1) return 1;
- if (mem[s][r] != -1)
- return mem[s][r];
- long long res = dp(s-1,r);
- for (int i = 1; i < r; ++i)
- res += 2*dp(s - 1, r - i);
- return mem[s][r] = res;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- scanf("%d %d", &m, &n);
- mem.resize(n+1,vector<long long>(m+1,-1));
- printf("%lld", dp(n,m));
- return 0;
- }
Editing is locked.