- #include <iostream>
- using namespace std;
-
- int shops[100005][3];
- int dp[100005][3];
-
- int shopping(int item, int i, int n)
- {
- if (dp[i][item] != -1)
- return dp[i][item];
-
- if (i == n - 1)
- {
- dp[i][item] = shops[i][item];
-
- return dp[i][item];
- }
- else
- {
- dp[i][item] = shops[i][item] + min(shopping((item + 1) % 3, i + 1, n),
- shopping((item + 2) % 3, i + 1, n));
-
- return dp[i][item];
- }
- }
-
- int main()
- {
- int t, n;
-
- cin >> t;
-
- while (t--)
- {
- cin >> n;
-
- for (int i = 0; i < n; i++)
- dp[i][0] = dp[i][1] = dp[i][2] = -1;
-
- for (int i = 0; i < n; i++)
- cin >> shops[i][0] >> shops[i][1] >> shops[i][2];
-
- int minimum = min(shopping(0, 0, n), shopping(1, 0, n));
- minimum = min(shopping(2, 0, n), minimum);
-
- cout << minimum << endl;
- }
-
- return 0;
- }
Language: C++