#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++