【DP】送你一颗圣诞树-白红宇的个人博客

【DP】送你一颗圣诞树

发布日期：2021-05-07 22:46:26 浏览次数：23 分类：精选文章

本文共 2468 字，大约阅读时间需要 8 分钟。

解题思路：

这道题涉及到树的结构优化问题，采用动态规划和记忆化技术来解决。我们需要计算每颗树的美观度，通过递归和拆分树的方法来处理树的结构。

步骤如下：

定义函数和数据结构：

dis[N] 用于存储同一颗树上两个点之间的距离。

top[N] 用于存储同一颗树上所有点到某特定点的距离。

ans[N] 用于存储每颗树的美观度。

size[N] 用于存储每颗树的大小。

计算距离函数 disx：

递归拆分树的结构，分别计算从x到y的距离。

使用记忆化技术，存储已经计算过的结果，避免重复计算。

计算到达点x的距离 topx：

根据树的结构，拆分树的点，分别计算从各个子树到x点的距离。

组合各子树的结果，计算整体的到达距离。

递归处理树的结构：

递归拆分树的结构，分别处理两棵子树。

计算每颗树的美观度，通过组合子树的结果来得到整颗树的结果。

处理输入数据并计算美观度：

读取输入数据，初始化各个数据结构。

递归计算每颗树的美观度，输出结果。

代码如下：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
#include 
       
        
#include 
        
          #define LL long long #define N 101 #define mod 1000000007 using namespace std; map
         
          
           , LL> dis[N]; map
           
             top[N]; LL T, m, a[N], b[N], c[N], d[N], l[N], ans[N], size[N]; LL disx(LL nowt, LL x, LL y) { if (x == y) return 0; if (x > y) swap(x, y); pair
            
              p = make_pair(x, y); if (dis[nowt].find(p) != dis[nowt].end()) { return dis[nowt][p]; } if (y < size[a[nowt]]) { dis[nowt][p] = (disx(a[nowt], x, y) + l[nowt]) % mod; disx(a[nowt], x, y); } else if (x >= size[a[nowt]]) { dis[nowt][p] = (disx(b[nowt], x - size[a[nowt]], y - size[a[nowt]]) + l[nowt]) % mod; disx(b[nowt], x - size[a[nowt]], y - size[a[nowt]]); } else { LL d1 = disx(a[nowt], x, c[nowt]) + l[nowt]; LL d2 = disx(b[nowt], y - size[a[nowt]], d[nowt]); dis[nowt][p] = (d1 + d2) % mod; } return dis[nowt][p]; } LL topx(LL nowt, LL x) { if (nowt == 0) return 0; if (top[nowt].find(x) != top[nowt].end()) { return top[nowt][x]; } if (x < size[a[nowt]]) { top[nowt][x] = (topx(a[nowt], x) + topx(b[nowt], d[nowt])) % mod; topx(a[nowt], x); } else { top[nowt][x] = (topx(b[nowt], x - size[a[nowt]]) + topx(a[nowt], c[nowt])) % mod; topx(b[nowt], x - size[a[nowt]]); top[nowt][x] = (topx(a[nowt], c[nowt]) * size[b[nowt]] % mod + topx(b[nowt], d[nowt]) * size[a[nowt]] % mod) % mod; } return top[nowt][x]; } void work() { scanf("%lld", &m); size[0] = 1; for (LL i = 1; i <= m; ++i) { scanf("%lld%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i], &l[i]); dis[i].clear(); top[i].clear(); size[i] = size[a[i]] + size[b[i]]; ans[i] = (ans[a[i]] + ans[b[i]]) % mod; ans[i] = (ans[i] + (size[a[i]] % mod) * (size[b[i]] % mod) % mod * (l[i] % mod) % mod) % mod; LL t1 = topx(a[i], c[i]); ans[i] = (ans[i] + (t1 % mod) * (size[b[i]] % mod) % mod) % mod; LL t2 = topx(b[i], d[i]); ans[i] = (ans[i] + (t2 % mod) * (size[a[i]] % mod) % mod) % mod; printf("%lld\n", ans[i]); } } int main() { scanf("%lld", &T); while (T--) { work(); } }

注：以上代码经过优化，适合用于在线评测。代码逻辑清晰，结构合理，便于理解和修改。

上一篇：【DFS】【暴力】KC看星(star)

下一篇：【gcd】【桶】【伪暴力】欠扁的CD

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章