60分过样例求调
查看原帖
60分过样例求调
542199
dxt_楼主2024/5/18 15:29
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,a[N],b[N],c[N];
long long dp[N][3],ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	dp[1][0]=a[1];dp[1][1]=b[1];dp[1][2]=c[1];
	for(int k=0;k<=2;++k){//k代表第一棵树的栽种种类 
	if(k==0) dp[2][1]=b[2]+dp[1][0],dp[2][2]=c[2]+dp[1][0];
	if(k==1) dp[2][0]=a[2]+dp[1][1],dp[2][2]=c[2]+dp[1][2];
	if(k==2) dp[2][0]=a[2]+dp[1][2],dp[2][1],b[2]+dp[1][2];
	for(int i=3;i<n;++i){
		dp[i][0]=a[i]+max(dp[i-2][0]+b[i-1],dp[i-1][2]);
		dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]=c[i]+max(dp[i-2][2]+b[i-1],dp[i-1][0]);
	}
	if(k!=0) ans=max(ans,a[n]+max(dp[n-2][0]+b[n-1],dp[n-1][2]));
	if(k!=2) ans=max(ans,c[n]+max(dp[n-2][2]+b[n-1],dp[n-1][0]));
	if(k==0) ans=max(ans,b[n]+dp[n-1][0]);
	if(k==2) ans=max(ans,b[n]+dp[n-1][2]);
/*	printf("%d  %d\n",k,ans);
	for(int i=1;i<=n;++i){
	for(int j=0;j<3;++j)
	printf("%d ",dp[i][j]);
	printf("\n");
	}*/
	}
	printf("%d",ans);
	return 0;
}
2024/5/18 15:29
加载中...