# include bits stdc using namespace std define MAXN 100010 define MAX ma

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47``` ```#include using namespace std; #define MAXN 100010 #define MAX(a,b,c) max(a,max(b,c)) #define FOR(i,s,e) for(int i=s; i<=e; i++) int cost[MAXN][4], memo[MAXN][2][2][2][4]; int n; class fastio { public: fastio() { ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); } } __fastio; int f(int i, int ka, int kb, int kc, int phase) { if(i > n) return 0; if(memo[i][ka][kb][kc][phase] != -1) return memo[i][ka][kb][kc][phase]; if(ka == 1) { if(kb > kc) return memo[i][ka][kb][kc][phase] = f(i+1, 0, 1, 0, 1) + cost[i][1]; else if(kc > kb) return memo[i][ka][kb][kc][phase] = f(i+1, 0, 0, 1, 1) + cost[i][1]; else return memo[i][ka][kb][kc][phase] = max(f(i+1, 0, 1, 0, 1) + cost[i][1], f(i+1, 0, 0, 1, 1) + cost[i][1]); } if(kb == 1) { if(ka > kc) return memo[i][ka][kb][kc][phase] = f(i+1, 1, 0, 0, 2) + cost[i][2]; else if(kc > ka) memo[i][ka][kb][kc][phase] = f(i+1, 0, 0, 1, 2) + cost[i][2]; else return memo[i][ka][kb][kc][phase] = max(f(i+1, 1, 0, 0, 2) + cost[i][2], f(i+1, 0, 0, 1, 2) + cost[i][2]); } if(kc == 1) { if(ka > kb) return memo[i][ka][kb][kc][phase] = (i+1, 1, 0, 0, 3) + cost[i][3]; else if(kb > ka) return memo[i][ka][kb][kc][phase] = f(i+1, 0, 1, 0, 3) + cost[i][3]; else return memo[i][ka][kb][kc][phase] = max(f(i+1, 1, 0, 0, 3) + cost[i][3], f(i+1, 0, 1, 0, 3) + cost[i][3]); } } void solve() { cin >> n; FOR(i,1,n) { cin >> cost[i][1] >> cost[i][2] >> cost[i][3]; } memset(memo, -1, sizeof(memo)); cout << MAX(f(1,1,0,0,1), f(1,0,1,0,2), f(1,0,0,1,3)) << endl; } int main() { __fastio; solve(); return 0; } ```