題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的序列，現(xiàn)在要求拆分成兩個子序列，使得兩個子序列的貢獻之和最 大。對于一個序列的貢獻就是，去掉相鄰且相同的字母后的長度，即 ${\sum }_{i=1}^n[a[i]!=a[i?1]]$，其中 $a[0]=0$。

題目分析：首先預(yù)處理出對于每個位置 $i$ 后首次出現(xiàn) $a_i$ 的位置，即為 $last[i]$，然后按照三個規(guī)則貪心即可：設(shè) $v1$ 為第一個序列的結(jié)尾位置，$v2$ 為第二個序列的結(jié)尾位置，默認為 $v1=v2=0$，對于第 $i$ 個位置的數(shù)：

如果 $a[i]=a[v1]$，那么將 $a[i]$ 加在第一個序列后面的貢獻為 $0$，所以應(yīng)該加到第二個序列后

如果 $a[i]=a[v2]$，根據(jù)規(guī)則 $1$ 同理可得將 $a[i]$ 加在第一個序列后面是更優(yōu)的

如果 $a[i],a[v1],a[v2]$ 互不相同，我們需要將 $a[i]$ 加到 $last[v1]$ 和 $last[v2]$ 較小的那個序列后

規(guī)則一和規(guī)則二比較容易想到，主要是規(guī)則三，我先放上一組反例，假如第一個序列此時為 $[1]$，第二個序列此時為 $[2]$，剩余需要分配的原序列為 $[3,2,2]$，如果將下一個 $3$ 加入序列一的話，那么第二個 $2$，無論如何也無法起到貢獻，所以應(yīng)該將這個 $3$ 加入到序列二中

感性理解一下規(guī)則三的話，就是 $last$ 更小的那個位置，可以更早的將當(dāng)前新加入的數(shù)字代替掉，這樣貢獻肯定只會越來越大

實現(xiàn)就比較簡單了

代碼：

// Problem: D1. Painting the Array I // Contest: Codeforces - Codeforces Round #700 (Div. 2) // URL: https://codeforces.com/contest/1480/problem/D1 // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int a[N],nt[N],last[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) {read(a[i]);last[i]=n+1;}last[0]=n+1;for(int i=n;i>=0;i--) {nt[i]=last[a[i]];last[a[i]]=i;}int ans=0,v1=0,v2=0;for(int i=1;i<=n;i++) {if(a[i]==a[v1]) {ans+=(a[i]!=a[v2]);v2=i;} else if(a[i]==a[v2]) {ans+=(a[i]!=a[v1]);v1=i;} else if(nt[v1]<nt[v2]) {ans++;v1=i;} else {ans++;v2=i;}}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1480D1 Painting the Array I(贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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