（一定要先贴一下wz大佬对这道题的定位：
）
另外说一句：我终于在拖了nnnnnnnnn天之后做完了这道题
算法标签：（其实也用不到辽上面都有）但我就是要贴一下咬我啊）
好啦好啦，上
- 思路：
首先为了节省空间，我令1=>0 2=>1；开了一个二维数组f[i][1/0]（为什么开f呢，因为发）用f[i][1]代表第i项为2时需要改动的最小个数，用f[i][0]表示第i项为1时需要改动的最小个数。这样形成递推：
for(int i=2;i<=n;i++) { if(a[i]==1){//第i个数为1时
f[i][0]=f[i-1][0];//如果不改动这个数，
那么最小值就等于上一个数为1时的值 f[i][1]=min(f[i-1][1],f[i-1][0])+1;//若改为2，那么前面的i-1个数
可以选择全置为1或全置为2，取两个中最小的，
再加上改动的1 } if(a[i]==2){//第i个数为2时 f[i][1]=min(f[i-1][0],f[i-1][1]);//保持第i个数为2，则前i-1个数可以全为1
也可以全为2，取其中较小的，赋给f[i][1]； f[i][0]=f[i-1][0]+1;//改变第i个数为1，那么前面必须全为1，
那么f[i][0]就为f[i-1][0]+1； } }
最后求出f[n][1]和f[n][0],比较他们的值，选择较小的一个输出
- 代码：（赶脚好low哦
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; int n,a[100000];//我也不知道为啥要开这么大，好看 int f[30001][2]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[1][2-a[1]]=1; f[1][a[1]-1]=0; for(int i=2;i<=n;i++) { if(a[i]==1){ f[i][0]=f[i-1][0]; f[i][1]=min(f[i-1][1],f[i-1][0])+1; } if(a[i]==2){ f[i][1]=min(f[i-1][0],f[i-1][1]); f[i][0]=f[i-1][0]+1; } } int ans=min(f[n][0],f[n][1]); printf("%d",ans); }
end-