【算法】动态规划
【题解】DP有个特点(递推的特点)，就是记录所有可能状态然后按顺序转移。
最优化问题中DP往往占据重要地位。
f[i][j]表示前i头奶牛，第i头改为号码j的最小改动数字，这样每头奶牛改为哪个编号的方案全部记录了，转移可以保证最优。
正反各做一次。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,f[maxn][],a[maxn];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
f[][]=f[][]=f[][]=;
for(int i=;i<=n;i++)
{
f[i][]=f[i-][]+(a[i]!=);
f[i][]=min(f[i-][],f[i-][])+(a[i]!=);
f[i][]=min(min(f[i-][],f[i-][]),f[i-][])+(a[i]!=);
}
int ans=min(min(f[n][],f[n][]),f[n][]);
f[n+][]=f[n+][]=f[n+][]=;
for(int i=n;i>=;i--)
{
f[i][]=f[i+][]+(a[i]!=);
f[i][]=min(f[i+][],f[i+][])+(a[i]!=);
f[i][]=min(min(f[i+][],f[i+][]),f[i+][])+(a[i]!=);
}
ans=min(ans,min(f[][],min(f[][],f[][])));
printf("%d",ans);
return ;
}