一维dp题解

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const int N = 3e5 + 20;
const int INF = 0x3f3f3f3f;
const LL INFLL =0x3f3f3f3f3f3f3f3f;
int a[N],b[N],c[N];
int dpa[N] , dpb[N] , dpc[N];
void so() {
		int n;
		cin >> n;
		for(int i = 1 ; i <= n ; i++ ) {
			cin >> a[i] >> b[i] >> c[i];
		}
        //dpa,dpb,dpc 的数组代表了当前用了第a/b/c样物体的最大值
 
		for(int i = 1 ; i <= n ; i++ ){
			dpa[i] = max(dpb[i - 1] , dpc[i - 1]) + a[i];  // 假设这次选了a, 那这次的最大值就是从上一次的b和c中取最大值再加上当前的a值
			dpb[i] = max(dpa[i - 1] , dpc[i - 1]) + b[i]; // 假设这次选了b, 那这次的最大值就是从上一次的a和c中取最大值再加上当前的b值
			dpc[i] = max(dpb[i - 1] , dpa[i - 1]) + c[i]; // 假设这次选了c, 那这次的最大值就是从上一次的a和b中取最大值再加上当前的c值
		}
		cout << max(max(dpa[n] , dpb[n]) , dpc[n]) <<endl;
}
int main() {
    IOS
    int tt=1;
  //  cin >> tt;
    while (tt--)
    so();
}