题解 P5144 【蜈蚣】
流逝丶
2019-09-23 21:07:41
区间DP题
是时候补补我的$dp$了，毕竟我太菜了。
首先是区间的异或，应该很容易想到前缀异或和
看到题目，区间转移，最大值，这不区间dp吗
很快想到状态$f[i][j]$，$i$表示已经分成了$i$段，$j$表示砍到了位置$j$
那么如何转移呢，区间DP最大的特点就是$3$层$for$，第二三层枚举的是区间端点，第一层枚举断点。
那么在这道题我们第一层显然是要枚举段数，
那么转移方程就有了$f[k+1][j]=max(f[k+1][j],f[k][i]+(sum[j]~\hat{ }~ sum[i])$
然后最终答案就是$f[m][n]$了
最后还有初始状态，$f[1][j]=sum[j]$因为前$j$个位置只有一段的话就是$1$~$j$的异或和
然后上代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005,M=105;
int n,m,x;
int sum[N],f[M][N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&x);
sum[i]=sum[i-1]^x;
}
for(int i=1;i<=n;++i)
f[1][i]=sum[i];
for(int k=1;k<=m;++k)
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
f[k+1][j]=max(f[k+1][j],f[k][i]+(sum[j]^sum[i]));
printf("%d\n",f[m][n]);
return 0;
}
```