题意
给定(n)个整数(a_i)和一个整数(m)。请找到(n)个非负整数 ，满足(b_0 <b_1<b_2< dots <b_ n)并且(sum ext{popcount}(b_i) imes a_i)的值最大
(1 le n le 200，n-1 le m le 10^{18})
思路
如果(m)比较小，这道题就是显然区间( ext{dp})，(a[l,r])对应([L,R])节点。但现在(m)特别大，因为有用到二进制位，我们就能想到用( ext{trie})树。蒟蒻第一反应：能建的出吗？但是我们发现，如果每一个( ext{trie})节点下面都是满的，它们都是一样的。也就是我们把(m cdot ext{log} m)个节点，归为的两类结点，第二维(m*m)的复杂度降为了(2)。
如果从下往上合并，我们只要关注这个点是否是满点，以及当前这下一层的贡献，([l,k])归到左儿子无贡献，那些归到右儿子加上(a[k+1,r])的和。
- 对于一个满点来说，两个儿子也都是满点。
- 对于最后一个节点到根路径上的点，可能会没有右儿子，那么左儿子是非满点（并不是说下面不满，因为这样难考虑，我们只把最后的那个所在的都拉出来分一类特殊处理），只能全部放到右儿子；也有可能有满左儿子且有非满右节点，右节点贡献一倍的(a[k+1,r])。区间dp
来自蒟蒻zjy的瞎掰，看的人不会很多，有耐心看的人可能就我一个，你们如果真想研究可以去zsy大佬那儿看看
#include <bits/stdc++.h>
const int N=305;
using std::max;
typedef long long ll;
int n;
ll m,a[N],f[2][2][N][N];
int main(){
scanf("%d%lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++) a[i]+=a[i-1];
int now=0;
memset(f[now],-63,sizeof(f[now]));
for (int i=1;i<=n;i++) f[now][0][i][i]=f[now][1][i][i]=0;
for (int w=1;1ll<<(w-1)<=m;w++){
now=now^1;
memset(f[now],-63,sizeof(f[now]));
for (int len=1;len<=n;len++)
for(int l=1,r=len;r<=n;l++,r++){
f[now][0][l][r]=f[now^1][0][l][r]+max(0ll,a[r]-a[l-1]);
for (int k=l;k<r;k++)
f[now][0][l][r]=max(f[now][0][l][r],f[now^1][0][l][k]+f[now^1][0][k+1][r]+a[r]-a[k]);
if ((m>>(w-1))&1){
f[now][1][l][r]=max(f[now^1][0][l][r],f[now^1][1][l][r]+a[r]-a[l-1]);
for (int k=l;k<r;k++)
f[now][1][l][r]=max(f[now][1][l][r],f[now^1][0][l][k]+f[now^1][1][k+1][r]+a[r]-a[k]);
}else f[now][1][l][r]=f[now^1][1][l][r];
}
}
printf("%lld
",f[now][1][1][n]);
}
后记
大型补blog现场（补不完了）