link

題意： 給一個數組，讓你從頭開始選出一些數放在$A$數組中，剩下的放在$B$數組中，且是有序選擇，讓后把兩個數組中相鄰且相等的元素合并。
D1： 使合并后$Len(A)+Len(B)$最大。
D2： 使合并后$Len(A)+Len(B)$最小。

為了方便，先假設 A B 結尾選擇的數組下標分別為 p1 p2 。$next[i]$表示下標為$i$對應的值的下一個位置，$now$為當前遍歷到的數組下標。
先考慮D1：
因為要求最小，我們可以貪心的來往后面填數，我們分成如下情況：
(1) $a[now]==a[p1]$ 那么填在p2處更好
(2) $a[now]==a[p2]$ 那么填在p1處更好
(3) $next[p1]<next[p2]$ 那么填在p1更好，這個也比較值觀，比如當前數組$A$中最后的$a[p1]=7$，數組$B$中最后的$a[p2]=6$，而還沒有填的數依次為$a[now]=8,a[now+1]=6,a[now+2]=6$，這個時候$now$填在哪個合適呢？顯然是填在$B$數組合適，因為我們要盡量讓相同的數不合并，如果填在了$A$，那么會使得相同的合并。
對于D2
跟D1差不多，只需要改動一點，依舊分成以下幾種情況：
(1) $a[now]==a[p1]$ 那么填在p1處更好
(2) $a[now]==a[p2]$ 那么填在p2處更好
(3) $next[p1]<next[p2]$ 那么填在p2更好，因為填在p2可以盡可能的讓即將到來的$next[p1]$與$p1$合并。

D1：

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],pos[N],ne[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<=n;i++) pos[i]=n+1;for(int i=n;i>=0;i--){ne[i]=pos[a[i]];pos[a[i]]=i;}int ans=0,p1=0,p2=0;for(int i=1;i<=n;i++){if(a[i]==a[p1]) { ans+=a[i]!=a[p2]; p2=i; }else if(a[i]==a[p2]) { ans+=a[i]!=a[p1]; p1=i; }else if(ne[p1]<ne[p2]) { ans+=1; p1=i; }else { ans+=1; p2=i; }}printf("%d\n",ans);return 0; } /**/

D2：

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],pos[N],ne[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<=n;i++) pos[i]=n+1;for(int i=n;i>=0;i--){ne[i]=pos[a[i]];pos[a[i]]=i;}int ans=0,p1=0,p2=0;for(int i=1;i<=n;i++){if(a[i]==a[p1]) p1=i;else if(a[i]==a[p2]) p2=i;else if(ne[p1]>ne[p2]) { ans+=1; p1=i; }else { ans+=1; p2=i; }}printf("%d\n",ans);return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #700 (Div. 2) D1 D2. Painting the Array 思维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。