dp感觉没问题,但是答案不对(感觉是输出有问题)求dalao看看
查看原帖
dp感觉没问题,但是答案不对(感觉是输出有问题)求dalao看看
534415
nuo_x楼主2023/8/4 00:42
#include<bits/stdc++.h>
using namespace std;
int n,dp[100010][3][2];
int a[1000010][3];
int ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
			for(int k=0;k<2;k++)
				dp[1][j][k]=0;
		dp[1][i][0]=dp[1][i][1]=a[1][i];
		for(int p=2;p<=n;p++)
		{
			dp[p][0][0]=max(dp[p-1][1][1],dp[p-1][2][1])+a[p][0];
			dp[p][1][0]=dp[p-1][2][1]+a[p][1];
			dp[p][1][1]=dp[p-1][0][0]=a[p][1];
			dp[p][2][1]=max(dp[p-1][1][0],dp[p-1][0][0])+a[p][2]; 
		}
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,max(dp[n][i][0],dp[n][i][1]));
	cout<<ans;
	return 0;
}
2023/8/4 00:42
加载中...