#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll INF=2e18;
int n,m,x;
int a[N];
ll sum[N],tmp[N],f[N];
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)cin>>a[i];
    for (int i=1;i<=n;i++){
        cin>>x;
        sum[i]=sum[i-1]+x;
    }//前缀和
    for (int i=1;i<=m;i++)tmp[i]=-INF;//初始化
    for (int i=1;i<=n;i++){
        f[i]=max(f[i-1],sum[i]+tmp[a[i]]);
        tmp[a[i]]=max(tmp[a[i]],f[i-1]-sum[i-1]);
    }//动归
    cout<<f[n];
    return 0;
}

点赞点赞😄

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const long long INF=2e18;
int n,m;
int a[N];
long long sum[N],tmp[N],f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    for(int i=1;i<=m;i++)
    {
        tmp[i]=-INF;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=max(f[i-1],sum[i]+tmp[a[i]]);
        tmp[a[i]]=max(tmp[a[i]],f[i-1]-sum[i-1]);
    }
    cout<<f[n]<<endl;
    return 0;
}

#include<bits/stdc++.h>#HETAO845776 using namespace std; const int N=1e6+20; const long long INF=2e18; int n,m; int a[N]; long long sum[N],tmp[N],f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { int x; cin>>x; sum[i]=sum[i-1]+x; } for(int i=1;i<=m;i++) { tmp[i]=-INF; } for(int i=1;i<=n;i++) { f[i]=max(f[i-1],sum[i]+tmp[a[i]]); tmp[a[i]]=max(tmp[a[i]],f[i-1]-sum[i-1]); } cout<<f[n]<<endl; return 0; }