首页 > 代码库 > CodeForce-811C Vladik and Memorable Trip(动态规划)
CodeForce-811C Vladik and Memorable Trip(动态规划)
Vladik and Memorable Trip
CodeForces - 811C
有一个长度为 n 的数列,其中第 i 项为 ai。
现在需要你从这个数列中选出一些互不相交的区间,并且保证整个数列中所有相同的数都在同一个区间中或都不在任意一个区间中。
要求最大化每个区间所有数去重后的异或和的总和。输出这个总和。
预处理出每个数字第一个出现的位置和最后一个出现的位置。以及每个区间内不同数字的异或和。
dp[i]表示考虑到前i个人,最大值是多少。分情况讨论一下即可。
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <string> #include <cstring> using namespace std; #define _ ios::sync_with_stdio(false) const int MAXN = 5010; const int INF = 0xfffffff; typedef long long ll; int n; ll a[MAXN]; int l[MAXN], r[MAXN]; ll s[MAXN][MAXN]; int vis[MAXN]; ll dp[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%I64d", a + i); if (l[a[i]]) l[a[i]] = min(l[a[i]], i); else l[a[i]] = i; if (r[a[i]]) r[a[i]] = max(r[a[i]], i); else r[a[i]] = i; } for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); s[i][i] = a[i]; vis[a[i]] = 1; for (int j = i + 1; j <= n; j++) { if (!vis[a[j]]) { s[i][j] = s[i][j - 1] ^ a[j]; vis[a[j]] = 1; } else { s[i][j] = s[i][j - 1]; } } } dp[0] = 0; for (int i = 1; i <= n; i++) { int temp = a[i]; if (i == r[temp]) { int L = l[temp]; int ok = 1; for (int j = l[temp] + 1; j < r[temp]; j++) { if (r[a[j]] > i) { ok = 0; break; } L = min(l[a[j]], L); } if (ok) dp[i] = max(dp[i - 1], dp[L - 1] + s[L][i]); else dp[i] = dp[i - 1]; } else dp[i] = dp[i - 1]; } printf("%I64d\n", dp[n]); }
CodeForce-811C Vladik and Memorable Trip(动态规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。