蒟蒻求助
查看原帖
蒟蒻求助
212320
djwj323楼主2021/7/16 13:03

wa了5个点

#include <iostream>
#include <cstdio>
using namespace std;
long long n,map[100004][3];
long long dp[2][100004][3][3];
long long sum,i;
int main(){
	for(scanf("%lld",&n),i=1;i<=n;i++)  scanf("%lld%lld%lld",&map[i][0],&map[i][1],&map[i][2]);
	for(dp[0][1][0][0]=map[1][0],dp[0][1][1][1]=map[1][1],dp[0][1][2][2]=map[1][2],i=2;i<n;i++)
	{
		if(i%2==0)  dp[0][i][0][0]=max(dp[0][i-1][1][0],dp[0][i-1][2][0])+map[i][0],dp[0][i][0][1]=max(dp[0][i-1][1][1],dp[0][i-1][2][1])+map[i][0],dp[0][i][0][2]=max(dp[0][i-1][1][2],dp[0][i-1][2][2])+map[i][0],dp[0][i][1][0]=dp[0][i-1][2][0]+map[i][1],dp[0][i][1][1]=dp[0][i-1][2][1]+map[i][1],dp[0][i][1][2]=dp[0][i-1][2][2]+map[i][1];
		else  dp[0][i][1][0]=dp[0][i-1][0][0]+map[i][1],dp[0][i][1][1]=dp[0][i-1][0][1]+map[i][1],dp[0][i][1][2]=dp[0][i-1][0][2]+map[i][1],dp[0][i][2][0]=max(dp[0][i-1][0][0],dp[0][i-1][1][0])+map[i][2],dp[0][i][2][1]=max(dp[0][i-1][0][1],dp[0][i-1][1][1])+map[i][2],dp[0][i][2][2]=max(dp[0][i-1][0][2],dp[0][i-1][1][2])+map[i][2];
	}dp[0][n][0][1]=max(dp[0][n-1][1][1],dp[0][n-1][2][1])+map[n][0],dp[0][n][0][2]=max(dp[0][n-1][1][2],dp[0][n-1][2][2])+map[n][0],dp[0][n][1][2]=dp[0][n-1][2][2]+map[n][0],sum=max(sum,max(dp[0][n][0][1],max(dp[0][n][0][2],dp[0][n][1][2])));
	for(dp[1][1][0][0]=map[1][0],dp[1][1][1][1]=map[1][1],dp[1][1][2][2]=map[1][2],i=2;i<n;i++)
	{
		if(i%2==1)  dp[1][i][0][0]=max(dp[1][i-1][1][0],dp[1][i-1][2][0])+map[i][0],dp[1][i][0][1]=max(dp[1][i-1][1][1],dp[1][i-1][2][1])+map[i][0],dp[1][i][0][2]=max(dp[1][i-1][1][2],dp[1][i-1][2][2])+map[i][0],dp[1][i][1][0]=dp[1][i-1][2][0]+map[i][1],dp[1][i][1][1]=dp[1][i-1][2][1]+map[i][1],dp[1][i][1][2]=dp[1][i-1][2][2]+map[i][1];
		else  dp[1][i][1][0]=dp[1][i-1][0][0]+map[i][1],dp[1][i][1][1]=dp[1][i-1][0][1]+map[i][1],dp[1][i][1][2]=dp[1][i-1][0][2]+map[i][1],dp[1][i][2][0]=max(dp[1][i-1][0][0],dp[1][i-1][1][0])+map[i][2],dp[1][i][2][1]=max(dp[1][i-1][0][1],dp[1][i-1][1][1])+map[i][2],dp[1][i][2][2]=max(dp[1][i-1][0][2],dp[1][i-1][1][2])+map[i][2];
	}dp[1][n][2][0]=max(dp[1][n-1][0][0],dp[1][n-1][1][0])+map[n][2],dp[0][n][2][1]=max(dp[0][n-1][0][1],dp[1][n-1][1][1])+map[n][2],dp[1][n][1][0]=dp[1][n-1][0][0]+map[n][1],sum=max(sum,max(dp[1][n][2][0],max(dp[0][n][2][1],dp[0][n][1][0])));
	return printf("%lld",sum),0;
}
2021/7/16 13:03
加载中...