首页 > 其他 > 详细

LOJ3215「PA 2019」Muzyka pop

时间:2020-01-26 22:30:44      阅读:73      评论:0      收藏:0      [点我收藏+]

题意

给定\(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]\)的和。

  1. 对于一个满点来说,两个儿子也都是满点。
  2. 对于最后一个节点到根路径上的点,可能会没有右儿子,那么左儿子是非满点(并不是说下面不满,因为这样难考虑,我们只把最后的那个所在的都拉出来分一类特殊处理),只能全部放到右儿子;也有可能有满左儿子且有非满右节点,右节点贡献一倍的\(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\n",f[now][1][1][n]);
} 

后记

大型补blog现场(补不完了)

LOJ3215「PA 2019」Muzyka pop

原文:https://www.cnblogs.com/flyfeather6/p/12234956.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!