Wannafly挑戰賽21 C 大水題

題目連結：​​點我​​​ 連結：https://www.nowcoder.com/acm/contest/159/C

來源：牛客網

題目描述

現在給你N個正整數ai，每個數給出一“好數程度” gi（數值相同但位置不同的數之間可能有不同的好數程度）。對于在 i 位置的數，如果有一在j位置的數滿足 j < i 且 ai=aj，則你可以将位于[i,j]閉區間内的序列評為“好序列”，然後獲得∑gk(j≤k≤i)（此閉區間内“好數程度”之和）分數。

注意: 在所有情況下，每個數都隻能被一個”好序列”包含（隻能與其他相應數被評為”好序列”一次）；在符合要求的情況下，”好序列”的評定次數不受限制，且通過不同”好序列”獲得的分數可以累加。

輸入描述:

第一行有一個正整數N。

接下來的一行有N個正整數ai，表示意義如上。

（保證ai在32位整型範圍内）

接下來的一行有N個正整數gi，表示ai的”好數程度”。

（保證gi在64位整型範圍内）

輸出描述:

一個整數，你可以獲得的最大分數（通過不同”好序列”獲得的分數可以累加），保證答案在64位整型範圍内。

示例1

輸入

7

1 2 1 2 3 2 3

1 4 3 4 3 4 5

輸出

23

備注:

資料範圍 2≤N≤300000

for (int len = 1; len < n; len++) { //操作區間的長度
        for (int i = 0, j = len; j <= n; i++, j++) { //始末
            //檢查是否比對（非必須）
            for (int s = i; s < j; s++) {
                //update
            }
        }
    }      

#include<iostream>
#include<map>
#include<algorithm>
const int maxn=300000+10;
typedef long long ll;
using namespace std;
map<int,int> p;
int a[maxn],best[maxn],last[maxn];
ll dp[maxn],sum[maxn];
int main(){
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if(p.count(a[i])==0){
      p[a[i]]=i;
      
    }else{
      last[i]=p[a[i]];
      p[a[i]]=i;
    }
  }
  
  int lin;
  
  for(int i=1;i<=n;i++)
  {
    scanf("%lld", &sum[i]);
    sum[i] += sum[i-1];
  }
  ll ans=0;
  for(int i=1;i<=n;i++){
    if(last[i]!=0){ 
      dp[i]=dp[last[i]-1]+sum[i]-sum[last[i]-1];
      best[i]=last[i]-1;
      if(best[last[i]]!=0&&dp[best[last[i]]]+sum[i]-sum[best[last[i]]]>dp[i]){
        dp[i]=dp[best[last[i]]]+sum[i]-sum[best[last[i]]];
        best[i] = best[last[i]];
      }  //比如資料裡有3個2，就會比較前面那個2好一點，等到下次再遇到2時，再比較，但是
      //每次隻用比較前面那個2和最好的那個2就行
    }
    ans=max(ans,dp[i]);
  }
  printf("%lld\n",ans);
  return 0;
}