首页 > 代码库 > 【动态规划】 Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip
【动态规划】 Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip
划分那个序列，没必要完全覆盖原序列。对于划分出来的每个序列，对于某个值v，要么全都在该序列，要么全都不在该序列。
一个序列的价值是所有不同的值的异或和。整个的价值是所有划分出来的序列的价值之和。
求整个的价值的最大值
f(i)表示最后一个划分序列的右端点为i时，1~i的答案。
f(i)=max{max{f(j)}(1<=j<i)+xorsum(j+1,i)(j+1到i的区间合法)}(1<=i<=n)
需要在转移的时候，顺便处理f(i)的前缀max。
最终的答案就是所有f(i)的最大值。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[5010],f[5010],fpremax[5010],num[5010],cnts[5010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
++num[a[i]];
}
for(int i=1;i<=n;++i){
int no=0,xorsum=0;
memset(cnts,0,sizeof(cnts));
for(int j=i;j>=1;--j){
if(!cnts[a[j]]){
xorsum^=a[j];
++no;
}
++cnts[a[j]];
if(cnts[a[j]]==num[a[j]]){
--no;
}
if(!no){
f[i]=max(f[i],fpremax[j-1]+xorsum);
}
}
fpremax[i]=max(fpremax[i-1],f[i]);
}
printf("%d\n",fpremax[n]);
return 0;
}
【动态规划】 Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。