众所周知,这一种算法是错的(非环形处理方式)
#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?想不通其中的道理