题解 CF264C 【Choosing Balls】

题解- CF246C Choosing Balls

• 题目意思

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

• 

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

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

  显然对于上次颜色相同的只要即可，对于颜色不同的即于是我们只要去求即可。此时我们就要去维护最大值以及次大值。而且因为单调性我们可以做到更新最大值与次大值。

• 

#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;
}