70分求助
查看原帖
70分求助
1183074
xzy_AK_IOI楼主2025/1/1 19:18
#include<bits/stdc++.h>
using namespace std;
#define F(i,k,n) for (int i=k;i<=n;i++)
typedef long long ll;
const int N=1e5+10;
int dp[N][4][2];
/*
dp[i][j][0]代表考虑到第i个空格,种j*10高度的树,且现在的树比上一棵矮的最大代价
否则是比上一颗树高
*/
int a[N][4];
int n;
signed main(){
	cin>>n;
	F(i,1,n) F(j,1,3) cin>>a[i][j];
	F(j,1,3) dp[1][j][0]=dp[1][j][1]=a[1][j];
	F(i,2,n){
		F(j,1,3){
			F(k,j+1,3){
				dp[i][k][1]=max(dp[i-1][j][0]+a[i][k],dp[i][k][1]);
			}
			F(k,1,j-1){
				dp[i][k][0]=max(dp[i-1][j][1]+a[i][k],dp[i][k][0]);
			}
		}
	}
	int ans=-1;
	F(j,1,3){
		F(k,j+1,3){
			dp[1][k][1]=max(dp[n][j][0],dp[1][k][1]);
		}
		F(k,1,j-1){
			dp[1][k][0]=max(dp[n][j][1],dp[1][k][0]);
		}
	}
	F(i,1,3) ans=max(ans,max(dp[1][i][0],dp[1][i][1]));
	cout<<ans;
	return 0;
}
2025/1/1 19:18
加载中...