Advertisement
Asif_Anwar

LOJ-1047(Neighbor House)

Jun 2nd, 2021
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. //using namespace chrono;
  5.  
  6. typedef long long ll;
  7. typedef vector< int > vi;
  8. typedef vector < ll > V;
  9. typedef map<int, int > mp;
  10.  
  11. #define pb push_back
  12. #define FastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  13. #define F first
  14. #define S second
  15.  
  16. #define debug cout << -1 << endl;
  17. #define REP(i, a, b) for(int i=a; i<b; i++)
  18. #define f0r(i, n) for (int i = 0; i < n; ++i)
  19. #define f0r1(i, n) for (int i = 1; i <= n; ++i)
  20. #define r0f(i, n) for(int i=n-1; i>=0; i--)
  21. #define fore(a, x) for (auto& a : x)
  22. #define fori(i, a, b) for (int i = (a); i < (b); ++i)
  23.  
  24. #define MP make_pair
  25. #define UB upper_bound
  26. #define LB lower_bound
  27. #define nw cout << "\n"
  28.  
  29. #define issq(x) (((ll)(sqrt((x))))*((ll)(sqrt((x))))==(x))
  30. #define rev(v) reverse(v.begin(),v.end())
  31. #define asche cerr<<"Ekhane asche\n";
  32. #define rev(v) reverse(v.begin(),v.end())
  33. #define srt(v) sort(v.begin(),v.end())
  34. #define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
  35. #define all(v) v.begin(),v.end()
  36. #define mnv(v) *min_element(v.begin(),v.end())
  37. #define mxv(v) *max_element(v.begin(),v.end())
  38. #define valid(tx,ty) (tx>=0 && tx<n && ty>=0 && ty<m)
  39. #define one(x) __builtin_popcount(x)
  40. //#define pop pop_back
  41. #define setPrec(x) cout << fixed << setprecision(x)
  42. #define sz(a) (int)a.size()
  43. //#define fin cin
  44. //#define fout cout
  45. const int INF = 1e9;
  46. const ll INFL = 1e18;
  47. const double diff = 10e-6;
  48. const int maxn = 100005;
  49. const double PI = acos(-1);
  50. using namespace std;
  51.  
  52. // int dx[] = {-1, 0, 1};
  53. // int dy[] = {-1, 0, 1};
  54.  
  55. int n;
  56. int dp[22][3];
  57. int arr[22][3];
  58.  
  59. int dpF(int i, int last)
  60. {
  61.     if(i>n) return 0;
  62.     if(dp[i][last]!=-1) return dp[i][last];
  63.  
  64.     int op1 = INF, op2 = INF, op3 = INF;
  65.     if(last!=1) op1 = arr[i][1] + dpF(i+1, 1);
  66.     if(last!=2) op2 = arr[i][2] + dpF(i+1, 2);
  67.     if(last!=3) op3 = arr[i][3] + dpF(i+1, 3);
  68.  
  69.     return dp[i][last] = min({op1, op2, op3});
  70. }
  71.  
  72. void solve()
  73. {
  74.     memset(dp, -1, sizeof(dp));
  75.     cin >> n;
  76.     f0r1(i, n) {
  77.         f0r1(j, 3) cin >> arr[i][j];
  78.     }
  79.     cout << dpF(1, 0) << "\n";
  80. }
  81.  
  82. int main()
  83. {
  84.     FastIO;
  85.     int t;
  86.     t = 1;
  87.     cin >> t;
  88.     f0r(i, t) {
  89.         cout << "Case " << i+1 << ": ";
  90.         solve();
  91.     }
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement