Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Summary:

An integer array A of size n <= 5000 has entries which ranges from 1 to 5000. We pick disjoint segments of the array such that for each segment S:

1. If i in S, then any j s.t. a[j] == a[i] must also be in S

2. The score of S is computed as the XOR of its elements

Goal is to maximise the sum of scores of the chosen segments.

Solution:

I like this problem. This is solvable using a dynamic programming approach.

Suppose dp[i] is the maximum score we can get when we are only allowed to pick segments in A[0...i]. To find dp[i], we can:

1. Skip A[i]. So dp[i] is at least as good as dp[i-1].

2. Form a segment using A[i]. To do this we need to check a few things. First, say the smallest segment we can form (satisfying the above condition) is A[j...k] (i.e. j <= i && i <= k). Now, if k > i, then we cannot use A[i] to form the current segment, as we will be using elements beyond [0..i]. If k == i, then we know that dp[i] is at least as good as dp[j-1] + score of A[j...i].

With that, the implementation is quite straightforward.

Implementation:

#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <utility> #include <cstring> using namespace std; int main(){ int n; scanf("%d",&n); int a[5010]; vector<pair<int,int>> b; for (int i = 0; i < n; ++i) { scanf("%d",&a[i]); b.push_back({a[i], i}); } sort(b.begin(), b.end()); int r[5010][2]; int prev = b[0].second; for (int i = 1; i < n; ++i) { if (b[i].first == b[i-1].first) continue; int val = b[i-1].first; int last = b[i-1].second; r[val][0] = prev; r[val][1] = last; prev = b[i].second; } r[b.back().first][0] = prev; r[b.back().first][1] = b.back().second; int dp[5010]; int mark[5010]; for (int i = 0; i < n; ++i) { dp[i] = dp[i-1]; bool can_choose = true; int last = i; int cur = 0; memset(mark, 0, sizeof(mark)); for (int j = i; j >= last; --j) { if (r[a[j]][1] > i) { can_choose = false; break; } last = min(last, r[a[j]][0]); if (!mark[a[j]]) { cur ^= a[j]; mark[a[j]] = 1; } } if (!can_choose) continue; dp[i] = max((last - 1 >= 0 ? dp[last-1] : 0) + cur, dp[i-1]); } printf("%d\n",dp[n-1]); return 0; }

## No comments:

## Post a Comment