这两个版本之间的唯一区别是，此版本要求的是最大可能的答案。
荷马非常喜欢数组。今天，他正在绘制一个数组a1，a2，…，an，它具有白色和黑色两种颜色。 a1，a2，…，an的绘画分配由数组b1，b2，…，bn描述，bi指示ai的颜色（白色为0，黑色为1）。
根据绘画任务b1，b2，…，bn，将数组a拆分为两个新数组a（0）和a（1），其中a（0）是a和a中所有白色元素的子序列（1）是a中所有黑色元素的子序列。例如，如果a = [1,2,3,4,5,6]并且b = [0,1,0,1,0,0]，则a（0）= [1,3,5,6 ]和a（1）= [2,4]。
如果我们将c中具有相同值的所有相邻元素合并，则数组s1，c2，…，ck中表示为seg（c）的段数就是元素数。例如，[1,1,2,2,3,3,3,2]中的段数为4，因为合并具有相同值的相邻元素后数组将变为[1,2,3,2] 。特别是，空数组中的段数为0。
荷马想找到一个绘画作业b，根据该作业，a（0）和a（1）中的段数尽可能大，即seg（a（0））+ seg（a（1）） 。找到这个号码。
输入值
第一行包含一个整数n（1≤n≤105）。
第二行包含n个整数a1，a2，…，an（1≤ai≤n）。
输出量
输出单个整数，指示最大可能的段总数。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int n,a[maxn]; int is[maxn]; vector<pair<int,int> > p1,p2; int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",a+i); int ans=0; int tot=0; for (int i=1;i<=n;i++) { int j; for (j=i;j<=n;j++) if (a[j]!=a[i]) break; if (j-i>1) { p2.push_back(make_pair(a[i],i)); } p1.push_back(make_pair(a[i],i)); if (j-i==1) is[i]=1; i=j-1; } for (int i=0;i<p1.size();i++) { int j; for (j=i;j<p1.size();j++) if (p1[j].first!=p1[i].first) break; ans++; i=j-1; } for (int i=0;i<p2.size();i++) { int j; for (j=i;j<p2.size();j++) if (p2[j].first!=p2[i].first) break; ans++; i=j-1; } for (int i=1;i<p1.size()-1;i++) { if (!is[p1[i].second]) continue; int pp1=-1,pp2=-1; int l=1,r=p2.size(); while (l<=r) { int mid=(l+r)>>1; if (p2[mid-1].second<=p1[i].second) { pp1=mid-1; l=mid+1; } else { r=mid-1; } } l=1,r=p2.size(); while (l<=r) { int mid=(l+r)>>1; if (p2[mid-1].second>=p1[i].second) { pp2=mid-1; r=mid-1; } else { l=mid+1; } } if (pp1==-1||pp2==-1) { continue; } if (p2[pp1].first!=p2[pp2].first) continue; int j; for (j=i;j<p1.size()-1;j++) if (!is[p1[j].second]) break; int f=0; for (int k=i;k<j;k++) { if (p1[k].first!=p2[pp1].first&&p1[k+1].first!=p1[k-1].first) { f=1; } } if (f) ans++; i=j-1; } printf("%d\n",ans); }
1480D1.Painting the Array I（分类讨论）
原文：https://www.cnblogs.com/zhanglichen/p/14394550.html