92pts求调
查看原帖
92pts求调
848964
hzoi_Shadow楼主2023/2/18 20:31
#include<bits/stdc++.h>
using namespace std;
int d[30001],f[30001][4][3];
int main()
{
	int n,i,j,num,sum;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>d[i];
	}
	for(i=1,j=n;i<=n,j>=1;i++,j--)
	{
		if(d[i]==1)
		{
			f[i][2][1]=min(f[i-1][2][1],f[i-1][1][1])+1;
			f[i][1][1]=f[i-1][1][1]; 
			f[i][3][1]=min(f[i-1][3][1],min(f[i-1][1][1],f[i-1][2][1]))+1;
		}
		if(d[i]==2)
		{
			f[i][2][1]=min(f[i-1][2][1],f[i-1][1][1]);
			f[i][1][1]=f[i-1][1][1]+1; 
			f[i][3][1]=min(f[i-1][3][1],min(f[i-1][1][1],f[i-1][2][1]))+1;
		}
		if(d[i]==3)
		{
			f[i][2][1]=min(f[i-1][2][1],f[i-1][1][1])+1;
			f[i][1][1]=f[i-1][1][1]+1; 
			f[i][3][1]=min(f[i-1][3][1],min(f[i-1][1][1],f[i-1][2][1]));
		}
		if(d[j]==1)
		{
			f[j][2][2]=min(f[j+1][2][2],f[j+1][1][2])+1;
			f[j][1][2]=f[j+1][1][2]; 
			f[j][3][2]=min(f[j+1][3][2],min(f[j+1][1][2],f[j+1][2][2]))+1;
		}
		if(d[j]==2)
		{
			f[j][2][2]=min(f[j+1][2][2],f[j+1][1][2]);
			f[j][1][2]=f[j+1][1][2]+1; 
			f[j][3][2]=min(f[j+1][3][2],min(f[j+1][1][2],f[j+1][2][2]))+1;
		}
		if(d[j]==3)
		{
			f[j][2][2]=min(f[j+1][2][2],f[j+1][1][2])+1;
			f[j][1][2]=f[j+1][1][2]+1; 
			f[j][3][2]=min(f[j+1][3][2],min(f[j+1][1][2],f[j+1][2][2]));
		}
	}
	num=min(f[n][1][1],min(f[n][2][1],f[n][3][1]));
	sum=min(f[1][1][2],min(f[1][2][2],f[1][3][2]));
	cout<<min(num,sum);
	return 0;
} 
2023/2/18 20:31
加载中...