[ABC345E] Colorful Subsequence 讲解

zrl123456 · 2024-03-21 22:09:24 · 题解

一眼 dp （贪心）。

部分分 （有吗）：

我们通过思考发现贪心策略是不行的，那么我们考虑 dp。

设状态：

我们设 f_{i,j} 为循环到第 i 个球且选中了第 i 个球，并有 j 个球被删除能所得的最大价值（若取不到值便为负无穷）。
边界条件是 f_{0,0}=0，最后的答案是什么我们还需要思考一下：
故最后答案为：

设状态转移方程：

那么我们可以寻找一个球 p\ (j-1\le p\le i-1) 和一个值 f_{p,j-1}，也就是说我们假设倒数第二个没有被删除的球为 p，易得转移方程：

这样时间复杂度就是 O(nk^2)，考虑优化。

优化：

如果没有 c_p\ne c_i 的限制的话，这道题就变得非常简单，只需要边维护 f 数组，边计算最大值即可。
但这只是假设，有了这条限制我们该怎么办呢？
解决方法当然有，我们找到一个次大值 p'，使 c_{p'}\ne c_p 即可。
为什么呢？

• 若 c_p=c_i，则 c_{p'}\ne c_i，c_{p'} 为最优解。
• 若 c_p\ne c_i，则 c_p 本身就为最优解。

那么问题又来了，如何转移（定义最大值为 fmax，次大值为 smax，结尾 c 值为 lst，由于空间复杂度较大，故后面 f 压掉第一维）？

• 若 lst\ne c_j，则： 若**以前的** $f_j\ge fmax$：$smax=fmax,fmax=f_j,lst=c_j$。 若 $f_j\ge smax$：$smax=f_j$。
• 若 lst=c_j，则： 若 $f_j\ge fmax$：$fmax=f_j$。

这样，时间复杂度为 O(nk)，空间复杂度为 O(n)，可以通过。
代码：

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define T set<string>::iterator
using namespace std;
const int N=2e5+5;
int n,k,c[N],v[N],f[N],ans=-INF;
signed main(){
    fst;
    memset(f,-0x3f,sizeof(f));
    f[0]=0;
    cin>>n>>k;
    rep(i,1,n) cin>>c[i]>>v[i];
    rep(i,1,n-k){
        int first_max=f[i-1],second_max=-INF,copyc=c[i-1];
        rep(j,i,i+k){
            int copyf=f[j];
            if(c[j]!=copyc){
                f[j]=first_max+v[j];
                if(copyf>=first_max){
                    second_max=first_max;
                    first_max=copyf;
                    copyc=c[j];
                }else if(copyf>=second_max) second_max=copyf;
            }else{
                f[j]=second_max+v[j];
                if(copyf>=first_max) first_max=copyf;
            }
        }
    }
    rep(i,n-k,n) ans=max(ans,f[i]);
    if(ans>=0) cout<<ans;
    else cout<<-1;
    return 0;
}