Advertisement
Guest User

Untitled

a guest
Feb 14th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long  ll;
  6. typedef unsigned long long ull;
  7. typedef map <int, int> mii;
  8. typedef pair <int, int> pii;
  9. typedef pair <ll, ll> pll;
  10.  
  11. int const maxn = int(1e5 + 12);
  12. int const maxb = int(2e6 + 12);
  13. int const inf = int(1e9 + 7);
  14. ll const linf = ll(1e18 + 12);
  15. double const eps = 1e-7;
  16. double const pi = acos(-1);
  17. #ifdef _WIN32
  18.     #define I64 "%I64d"
  19. #else
  20.     #define I64 "%lld"
  21. #endif
  22. #define mp make_pair
  23. #define pb push_back
  24. #define F first
  25. #define S second
  26. //#define fn ""
  27.  
  28. ll dp[15][20];
  29.  
  30. int n;
  31.  
  32. ll rec(int len, int last)
  33. {
  34.     if (len == n)
  35.         return 1;
  36.     ll & ans = dp[last][len];
  37.     if (ans != -1)
  38.         return ans;
  39.     ans = 0;
  40.     for (int i = 0; i < 10; i++)
  41.         if (i != last)
  42.             ans += rec(len + 1, i);
  43.     return ans;
  44. }
  45.  
  46. int main()
  47. {
  48.     #ifdef fn
  49.         freopen(fn".in", "r", stdin);
  50.         freopen(fn".out", "w", stdout);
  51.     #endif
  52.     scanf("%d", &n);
  53.     memset(dp, -1, sizeof(dp));
  54.     printf(I64, rec(0,  0));
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement