P5144 蜈蚣

    • 148通过
    • 2.6K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    一群人在山上遇见了一条蜈蚣

    题目描述

    在一条山路的转角处,WYH发现了一条有中指一样粗的有N节的蜈蚣。这只蜈蚣马上就吸引了HKE的眼球,HKE深深地爱上了这条魔性的蜈蚣。它的很多对足在前进的时候像波浪一样,颇是有毒。

    但是,热爱解剖动物的MZL却准备把蜈蚣切了。HKE很失落,于是MZL承诺不会完全肢解它,只把它的N节切成M段,每一段包含原蜈蚣完整的一节或多节。

    HKE看到他心爱的蜈蚣会切掉是会觉得恶心的。蜈蚣的每一节都有一个权值W[i],切下来的一段(W[i],W[i+1],...,W[j])带给HKE的恶心值是W[i] xor W[i+1] xor ... xor W[j],这里的xor代表按位异或操作。邪恶的LJC希望HKE受到的总恶心值——也就是每一段子蜈蚣带给HKE的恶心值的和最大,请你求出HKE的最大恶心值。

    (注:按位异或,其运算符号在pascal中为xor,在c++中为^或xor;请注意加法与异或运算的优先级先后顺序)

    输入输出格式

    输入格式:

    第一行,两个整数N,M,表示蜈蚣长N节,切成M段。

    第二行N个整数用空格分开,表示蜈蚣每一节的权值W[1],W[2],...,W[n]。

    输出格式:

    一个整数表示最大恶心值。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 2 3 4 5
    
    输出样例#1: 复制
    15

    说明

    第一段的恶心值为 1 xor 2 = 3

    第二段的恶心值为 3 xor 4 = 7

    第三段的恶心值为 5

    总恶心值为 3+7+5=15。此时为最优解。

    对于30%的数据,1≤N≤100,1≤M≤10;

    对于100%的数据,1≤N≤1000,1≤M≤100,保证结果在2^30-1内;

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。