思路： 1.DP f[i][j]：前i个数 最后一个数是j的最小花费 f[i][j]=min(f[i][j],f[i-1][k]+(a[i]!=j));1<=k<=j 这种做法比较有普遍性… 2. 直接枚举断点乱搞不就行了嘛… 枚举在哪儿转折成的2 （注意全是1或者全是2的情况就OK了）
//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,a[55555],f[55555][2]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); memset(f,0x3f,sizeof(f)),f[0][1]=f[0][2]=0; for(int i=1;i<=n;i++) for(int j=1;j<=2;j++) for(int k=1;k<=j;k++) f[i][j]=min(f[i][j],f[i-1][k]+(a[i]!=j)); printf("%d\n",min(f[n][2],f[n][1])); } //By SiriusRen #include <cstdio> #include <algorithm> using namespace std; int n,a[55555],vis[55555],cnt; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]==1)cnt++; vis[i]=cnt; } int ans=cnt; for(int i=1;i<=n;i++)ans=min(ans,cnt-vis[i]+i-vis[i]); printf("%d\n",ans); }