【UNR#4】序列妙妙值分块+DP
只会 80pts.
最裸的暴⼒（40pts）
令 $f[i][j]$ 表⽰当前 DP 到 $i$，划分成了 $j$ 段的最⼩值.
时间复杂度 $O(n^2)$
⼀点优化（60 ~ 80pts)
有⼏个测点 $a[i]$ 很⼩，那么可以直接开⼀个桶 $s[i][j]$ 表⽰前缀异或和为 $i$，且划分 $j$ 段的最⼩值.
修改复杂度：$O(1)$，查询复杂度 $O(v)$，总复杂度 $O(nv)$.
还可以在 $trie$ 树上乱搞，不知道能拿多少分.
正解
分块.
我们发现 $60$ 分解法中查询和修改复杂度差异很⼤，所以考虑⽤分块去平衡上述复杂度.
由于数字最⼤是 $2^{16}$，所以考虑维护 $mi[x][y]$ 表⽰⼀个数的前 $8$ 位是 $x$，去匹配⼀个后 $8$ 位为 $y$ 的贡献.  那么这个修改起来的话只需要枚举后⾯的 $y$，复杂度为 $O(\sqrt v)$.
查询的话后⾯是固定的，然后枚举前⾯的 $x$，复杂度为 $O(\sqrt v)$.
总复杂度就是 $O(nK \sqrt v)$ 的.
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 60009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int inf=1000000000;
int n,K;
int a[N],f[N],tmp[N],mi[300][300];
int main() {
// setIO("input");
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
a[i]^=a[i-1];cstring转为int
}
f[0]=0;
for(int i=1;i<=n;++i) {
f[i]=inf;
}
int B=(1<<8)-1;
for(int i=1;i<=K;++i) {
for(int x=0;x<256;++x) {
for(int y=0;y<256;++y) mi[x][y]=inf;
}
for(int j=0;j<=n;++j) {
tmp[j]=inf;
for(int x=0;x<256;++x) {
//  前⾯固定，后⾯是猜的
int det=mi[x][a[j]&B]+((a[j]>>8^x)<<8);                  tmp[j]=min(tmp[j],det);
}
for(int x=0;x<256;++x) {
int cur=mi[a[j]>>8][x];
int det=f[j]+((a[j]&255)^x);
mi[a[j]>>8][x]=min(mi[a[j]>>8][x],det);              }
}
for(int j=0;j<=n;++j) f[j]=tmp[j];
}
for(int i=K;i<n;++i) printf("%d ",f[i]);
printf("%d",f[n]);
printf("\n");
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。