HDU 5735 Born Slippy(拆值DP+位运算)

发布时间:2017-3-28 4:32:43 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 5735 Born Slippy(拆值DP+位运算) ",主要涉及到HDU 5735 Born Slippy(拆值DP+位运算) 方面的内容,对于HDU 5735 Born Slippy(拆值DP+位运算) 感兴趣的同学可以参考一下。

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5735

 

【题目大意】

  给出一棵树,树上每个节点都有一个权值w,w不超过216,树的根为1,从一个点往根的方向走,可以得到他的祖先序列,现在需要从v1点的祖先序列中挑选出一定数量的点,组成数列v1,v2,v3……vm,要求vi是vi-1的祖先,求dp[v1]=max(dp[vi]+(w[v1] opt w[vi])),opt是一种运算,在题目中可为xor,or或者and,最后求出ans=sum_{i=1}^{n}(i*(w[i]+dp[i]))

【题解】

  对于这道题,我们首先考虑它的简化版本,在一个一维数组上求dp[i]=max(dp[j]+(w[i] opt w[j])) (j<i),显然枚举前缀的O(n2)的用脚趾头都能想出来的算法,出题人是不会给过的。那么我们观察一下题目,发现一个很奇巧的东西,w的值不超过216,难道说每次计算以w结尾的dp最大值,然后枚举二进制?一次6w多的计算量,明显也没有产生太大的优化,顺着这个思路下去,这道题采用了一种拆值DP的神奇的方式,

  dp[i]=max(dp[j]+([w[i]前八位]opt[w[j]前八位])<<8+[w[i]后八位]opt[w[j]后八位])

  记dp[A][B]=以前八位为A结尾,后八位以B结尾的dp值,于是就可以发现:

        dp[A][B]=max(dp[i][B]+([w[i]前八位]opt[w[A]前八位])<<8)

  那么,在知道了后八位的情况下,前八位就能轻松dp,既然这样,那我们就在计算完每个节点之后,预处理后八位的dp值:

        dp[A][i]=max(dp[A][j]+([w[i]后八位]opt[w[j]后八位]))

  这样子每次转移所需要的复杂度就只有28,可以接受。顺利完成。

  而这道题所处理的却是树上的问题,那么在每条链上DP的过程中预处理祖先节点dp数组,按照上述方法计算子节点的dp值即可,而对于不同的子节点,dp数组备份,然后回溯即可。

【代码】

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned int UI;
const int N=65540,mod=1e9+7;
UI T,n,i,w[N],nxt[N],x,f[256][256],tmp[N][256],v[256],ans;
vector<UI>g[N];
char op[5];
UI opt(UI a,UI b){
    if(op[0]=='A')return a&b;
    if(op[0]=='O')return a|b;
    if(op[0]=='X')return a^b;
}
void dfs(UI x){
    UI dp=0,A=w[x]>>8,B=w[x]&255;
    for(int i=0;i<256;i++)if(v[i])dp=max(dp,f[i][B]+(opt(A,i)<<8));
    ans=(1LL*x*(dp+w[x])+ans)%mod;
    for(v[A]++,i=0;i<256;i++)tmp[x][i]=f[A][i],f[A][i]=max(f[A][i],opt(B,i)+dp);
    for(int i=0;i<g[x].size();i++)dfs(g[x][i]);
    for(v[A]--,i=0;i<256;i++)f[A][i]=tmp[x][i];
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %s",&n,op);
        for(int i=1;i<=n;i++)scanf("%d",&w[i]),g[i].clear();
        for(int i=2;i<=n;i++)scanf("%d",&x),g[x].push_back(i);
        ans=0; dfs(1);
        printf("%d\n",ans);
    }return 0;

上一篇:java中的Comparable接口
下一篇:模板类 error LNK2019: 无法解析的外部符号

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款