想不通题解的思路过程,不知道自己的思路哪里错了
查看原帖
想不通题解的思路过程,不知道自己的思路哪里错了
209263
lizedong楼主2021/11/13 21:06

众所周知,这一种算法是错的(非环形处理方式)

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10,inf=1e8;
int ans=-inf,f[N][4][2],a[N],b[N],c[N],n;

inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0' || '9'<ch){
		if(ch=='-')f=-1;ch=getchar();
	}
	while('0'<=ch && ch<='9'){
		x=10*x+ch-'0',ch=getchar();
	}
	return f*x;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=read(),c[i]=read();
//	++n;
//	a[n]=a[1],b[n]=b[1],c[n]=c[1];
	for(int i=1;i<=n;i++)
	{
		f[i][1][0]=max(f[i-1][2][1],f[i-1][3][1])+a[i];
		f[i][2][1]=f[i-1][1][0]+b[i];
		f[i][2][0]=f[i-1][3][1]+b[i];
		f[i][3][1]=max(f[i-1][1][0],f[i-1][2][0])+c[i];
	};
	cout<<max(f[n][1][0],max(f[n][2][0],max(f[n][3][1],f[n][2][1])));
	return 0;
}

受到Eismcs大佬的启发,写了一个等价的AC代码

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10,inf=1e8;
int ans=-inf,f[N][4][2],a[N],b[N],c[N],n;

inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0' || '9'<ch){
		if(ch=='-')f=-1;ch=getchar();
	}
	while('0'<=ch && ch<='9'){
		x=10*x+ch-'0',ch=getchar();
	}
	return f*x;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=read(),c[i]=read();
	++n;
	a[n]=a[1],b[n]=b[1],c[n]=c[1];//移位
	for(int i=2;i<=n;i++)//for循环范围有变
	{
		f[i][1][0]=max(f[i-1][2][1],f[i-1][3][1])+a[i];
		f[i][2][1]=f[i-1][1][0]+b[i];
		f[i][2][0]=f[i-1][3][1]+b[i];
		f[i][3][1]=max(f[i-1][1][0],f[i-1][2][0])+c[i];
	};
	cout<<max(f[n][1][0],max(f[n][2][0],max(f[n][3][1],f[n][2][1])));
	return 0;
}

然后蒟蒻就想不通了,相较于第一个代码,只是把第一个元素放到最后就可以AC?环在移位后并没有改变,代码为何又能AC?想不通其中的道理

2021/11/13 21:06
加载中...