可以考虑DP
设 f [ i ] [ 1/2/3 ] [ 0/1 ] 表示当前考虑到第 i 头牛，打算让当前位置的编号变成 1/2/3，并且打算让整段序列上升/下降 0/1
然后就对每种情况慢慢考虑转移就行了
可以发现第一维可以直接优化掉，然后空间就是 O(1)，时间就是 O(n)
太简单就不用注释了吧...
#include#include #include #include #include using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}int n,f[4][2];int main(){ int a; n=read(); while(n--) { a=read(); if(a==1) { f[3][0]=min(f[3][0],min(f[2][0],f[1][0]))+1; f[2][0]=min(f[2][0],f[1][0])+1; f[1][1]=min(f[3][1],min(f[2][1],f[1][1])); f[2][1]=min(f[3][1],f[2][1])+1; f[3][1]=f[3][1]+1; continue; } if(a==2) { f[3][0]=min(f[3][0],min(f[2][0],f[1][0]))+1; f[2][0]=min(f[2][0],f[1][0]); f[1][0]=f[1][0]+1; f[1][1]=min(f[3][1],min(f[2][1],f[1][1]))+1; f[2][1]=min(f[3][1],f[2][1]); f[3][1]=f[3][1]+1; continue; } f[3][0]=min(f[3][0],min(f[2][0],f[1][0])); f[2][0]=min(f[2][0],f[1][0])+1; f[1][0]=f[1][0]+1; f[1][1]=min(f[3][1],min(f[2][1],f[1][1]))+1; f[2][1]=min(f[3][1],f[2][1])+1; } int ans=1e9+7; for(int i=1;i<=3;i++) for(int j=0;j<=1;j++) ans=min(ans,f[i][j]); printf("%d",ans); return 0;}