题解 CF264C 【Choosing Balls】

题解- CF246C Choosing Balls

题目意思

说人话就是你可以选若干个物品，若这次选择的物品与上次选的 $c_i$ 相同那么这个的贡献就是 $a*v_i$ 否则是 $b*v_i$ 。要使得利益最大化。
$Sol$

一开始我以为是什么贪心。后来想想认为还是一个 $Dp$ 。就是要利用其特殊的一个性质单调性

我们设 $f_i$ 表示到现在选择的最后一个元素的颜色为 $i$ 的最优解。

显然对于上次颜色相同的只要 $f_i=f_i+v_i*a$ 即可，对于颜色不同的即 $f_i=\max{[f_j]+v_i*b}$ 于是我们只要去求 $\max{[f_j(j!=i)]}$ 即可。此时我们就要去维护最大值以及次大值。而且因为单调性我们可以做到 $O(1)$ 更新最大值与次大值。
$Code$

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;

int n,m,a[N],c[N],f[N],las,ans,ret;

signed main()
{
    scanf("%lld%lld",&n,&m);
    for ( int i=1;i<=n;i++ ) scanf("%lld",&a[i]);
    for ( int i=1;i<=n;i++ ) scanf("%lld",&c[i]);
    for (;m--;)
    {
        int A,B;
        scanf("%lld%lld",&A,&B);
        memset(f,-63,sizeof(f));
        ans=0;
        int lp=0,lb=0;
        for ( int i=1;i<=n;i++ ) 
        {
            ans=max(B*a[i],f[c[i]]+A*a[i]);
            if(c[i]!=lp) ans=max(ans,f[lp]+B*a[i]);
            else ans=max(ans,f[lb]+B*a[i]);
            if(ans>f[lp])
            {
                if(lp!=c[i]) lb=lp,lp=c[i];
                else lp=c[i];
            }
            else 
                if(ans>f[lb]&&c[i]!=lp) lb=c[i];
            f[c[i]]=max(f[c[i]],ans);
            ret=max(ret,ans);
        }
        printf("%lld\n",ret);
        ret=0;
    }
    return 0;
}