link

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

為了方便，先假設(shè) A B 結(jié)尾選擇的數(shù)組下標(biāo)分別為 p1 p2 。$next[i]$表示下標(biāo)為$i$對(duì)應(yīng)的值的下一個(gè)位置，$now$為當(dāng)前遍歷到的數(shù)組下標(biāo)。
先考慮D1：
因?yàn)橐笞钚?#xff0c;我們可以貪心的來往后面填數(shù)，我們分成如下情況：
(1) $a[now]==a[p1]$ 那么填在p2處更好
(2) $a[now]==a[p2]$ 那么填在p1處更好
(3) $next[p1]<next[p2]$ 那么填在p1更好，這個(gè)也比較值觀，比如當(dāng)前數(shù)組$A$中最后的$a[p1]=7$，數(shù)組$B$中最后的$a[p2]=6$，而還沒有填的數(shù)依次為$a[now]=8,a[now+1]=6,a[now+2]=6$，這個(gè)時(shí)候$now$填在哪個(gè)合適呢？顯然是填在$B$數(shù)組合適，因?yàn)槲覀円M量讓相同的數(shù)不合并，如果填在了$A$，那么會(huì)使得相同的合并。
對(duì)于D2
跟D1差不多，只需要改動(dòng)一點(diǎn)，依舊分成以下幾種情況：
(1) $a[now]==a[p1]$ 那么填在p1處更好
(2) $a[now]==a[p2]$ 那么填在p2處更好
(3) $next[p1]<next[p2]$ 那么填在p2更好，因?yàn)樘钤趐2可以盡可能的讓即將到來的$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; } /**/

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。