1. #include <iostream>
  2. using namespace std;
  3.  
  4. int shops[100005][3];
  5. int dp[100005][3];
  6.  
  7. int shopping(int item, int i, int n)
  8. {
  9. if (dp[i][item] != -1)
  10. return dp[i][item];
  11.  
  12. if (i == n - 1)
  13. {
  14. dp[i][item] = shops[i][item];
  15.  
  16. return dp[i][item];
  17. }
  18. else
  19. {
  20. dp[i][item] = shops[i][item] + min(shopping((item + 1) % 3, i + 1, n),
  21. shopping((item + 2) % 3, i + 1, n));
  22.  
  23. return dp[i][item];
  24. }
  25. }
  26.  
  27. int main()
  28. {
  29. int t, n;
  30.  
  31. cin >> t;
  32.  
  33. while (t--)
  34. {
  35. cin >> n;
  36.  
  37. for (int i = 0; i < n; i++)
  38. dp[i][0] = dp[i][1] = dp[i][2] = -1;
  39.  
  40. for (int i = 0; i < n; i++)
  41. cin >> shops[i][0] >> shops[i][1] >> shops[i][2];
  42.  
  43. int minimum = min(shopping(0, 0, n), shopping(1, 0, n));
  44. minimum = min(shopping(2, 0, n), minimum);
  45.  
  46. cout << minimum << endl;
  47. }
  48.  
  49. return 0;
  50. }
Language: C++