https://www.nowcoder.com/acm/contest/159/C
dp
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <set> #include <map> #include <list> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <iostream> using namespace std; #define ll long long #define minv 1e-6 #define inf 1e9 const ll mod=1e9+7; const long maxn=3e5+5; struct node { int a,num; }p[maxn]; int pre[maxn]; ll g[maxn],tot[maxn],f[maxn][2]; int cmp(node x,node y) { if (x.a==y.a) return x.num<y.num; else return x.a<y.a; } int main() { int n,i; ll maxf=0; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&p[i].a); p[i].num=i; } sort(p+1,p+n+1,cmp); for (i=1;i<=n;i++) pre[i]=-1; for (i=2;i<=n;i++) if (p[i].a==p[i-1].a) pre[p[i].num]=p[i-1].num; tot[0]=0; for (i=1;i<=n;i++) { scanf("%lld",&g[i]); tot[i]=tot[i-1]+g[i]; } maxf=0; f[0][0]=0,f[0][1]=0; for (i=1;i<=n;i++) { f[i][0]=max(f[i-1][0],f[i-1][1]); if (pre[i]!=-1) f[i][1]=max(f[pre[i]][0]+tot[i]-tot[pre[i]-1] , f[pre[i]][1]-g[pre[i]]+tot[i]-tot[pre[i]-1]); else f[i][1]=0; } printf("%lld",max(f[n][0],f[n][1])); // maxf=0; // for (i=1;i<=n;i++) // { // f[i]=f[i-1]; // if (pre[i]!=-1) // f[i]=max(f[i-1],f[pre[i]]+tot[i]-tot[pre[i]-1]); // // } // printf("%lld",f[n]); return 0; } /* 7 1 1 1 2 1 1 1 1 2 3 1 4 5 6 7 1 2 1 4 7 1 7 1 1 1 1 1 1 10 */