给定\(n\)个整数\(a_i\)和一个整数\(m\)。请找到\(n\)个非负整数 ,满足\(b_0 <b_1<b_2< \dots <b_ n\)并且\(\sum \text{popcount}(b_i) \times a_i\)的值最大
\(1 \le n \le 200,n-1 \le m \le 10^{18}\)
如果\(m\)比较小,这道题就是显然区间\(\text{dp}\),\(a[l,r]\)对应\([L,R]\)节点。但现在\(m\)特别大,因为有用到二进制位,我们就能想到用\(\text{trie}\)树。蒟蒻第一反应:能建的出吗?但是我们发现,如果每一个\(\text{trie}\)节点下面都是满的,它们都是一样的。也就是我们把\(m \cdot \text{log} m\)个节点,归为的两类结点,第二维\(m*m\)的复杂度降为了\(2\)。
如果从下往上合并,我们只要关注这个点是否是满点,以及当前这下一层的贡献,\([l,k]\)归到左儿子无贡献,那些归到右儿子加上\(a[k+1,r]\)的和。
来自蒟蒻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\n",f[now][1][1][n]);
}
大型补blog现场(补不完了)
原文:https://www.cnblogs.com/flyfeather6/p/12234956.html