---
title: Codeforce 811 C. Vladik and Memorable Trip 解析(思維、DP)
description: "Codeforce 811 C. Vladik and Memorable Trip 解析(思維、DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 811 C. Vladik and Memorable Trip 解析(思維、DP)">
<!-- toc -->

# Codeforce 811 C. Vladik and Memorable Trip 解析(思維、DP)
今天我們來看看CF811C
[題目連結](https://codeforces.com/problemset/problem/811/C)

> **題目**
給你一個數列，一個區段的數列的值是區段內所有**相異**數的$XOR$總和。你可以選任意多的區段，求最大的所有區段的值的總和。然而所有同樣的數字不是完全沒有被包含在區段裡，不然就是要全部在同個區段裡。

### 前言
這題我一直到看了解答才知道為什麼不是$O(n)$，題目一直沒搞清楚

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
這題的難點在，很難用$O(n^2)$以下找到一個真正的可行的區段。
此題的做法是線性DP，$dp[i]$為考慮到數列的第$i$個時的解答，而要計算$i+1$，我們只需要多考慮是否有個區段是在$i+1$結尾。
首先可以$O(n)$得到每個數字最左和最右邊在哪裡，每當要計算$dp[i+1]$時，先看看$i+1$這個位置是否是某個數字的最右的位置，接著從$i+1$位置開始往回看，如果目前看的元素的最右位置超出$i+1$，代表目前$i+1$不可能是某個區段的結尾，那麼$dp[i+1]=dp[i]$；如果一切正常，直到目前位置已經到了目前看過的所有元素的最左位置，就代表我們已經找到一個結尾在$i+1$的區段了，此時$dp[i+1]=\max\{dp[i],區段的$XOR$+$dp[區段的最左-1]$\}$

官方解答有個Challenge，利用$a\oplus b\le a+b$，可以應付$n,a[i]\le1e5$的情況，待之後想到再補吧!

### 程式碼:

const int _n=5010;
int t,n,a[_n],dp[_n];
bool vis[_n],has[_n];
PII alr[_n];
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,1,n+1){
    cin>>a[i];if(!alr[a[i]].fi)alr[a[i]].fi=i;
    alr[a[i]].se=i;
  }rep(i,1,n+1)if(alr[a[i]].se==i)has[i]=1;
  dp[0]=0,dp[1]=(has[1]?a[1]:0);rep(i,2,n+1){
    dp[i]=dp[i-1];
    if(has[i]){
      int val=0,L=alr[a[i]].fi;memset(vis,0,sizeof vis);
      int j=i;while(j>=L){
        if(alr[a[j]].se>i)goto A;
        L=min(L,alr[a[j]].fi);
        if(!vis[a[j]])val^=a[j],vis[a[j]]=1;j--;
      }
      dp[i]=max(dp[i],val+dp[L-1]);
    }
    A:;
  }cout<<dp[n]<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/811/submission/91639328)