社区讨论

这种类型的dp可以优化吗

2025/11/30 12:06学术版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

来源于 NOIP T3 的 O(n*4^n) 暴力状压

CPP

for(int i=0;i<(1<<n);i++){
    for(int j=0;j<(1<<n);j++){
        h[i|j]=max(h[i|j],f[i]+g[j]);
    }
}

问了很多 ai，它们无一不都给出了先对 f 和 g 做 SOS dp，再做一遍逆变换的结果，但显然这个 max 是没有逆运算的，所以这种转移到底有没有优化方法？

共 0 条回复，欢迎继续交流。

正在加载回复...