热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

JSOI2015Salesman(树型DP)

【luogu6082】【题目描述】某售货员小T要到若干城镇去推销商品,由于该地区是交通不便的山区,任意两个城镇之间都只有唯一的可能经过其它城镇的路线。小T可以准确地估计出在每个城镇

【luogu6082】

 【题目描述】

某售货员小T要到若干城镇去推销商品,由于该地区是交通不便的山区,任意两个城镇之间都只有唯一的可能经过其它城镇的路线。

小T 可以准确地估计出在每个城镇停留的净收益。这些净收益可能是负数,即推销商品的利润抵不上花费。

由于交通不便,小T经过每个城镇都需要停留,在每个城镇的停留次数与在该地的净收益无关,因为很多费用不是计次收取的,而每个城镇对小T的商品需求也是相对固定的,停留一次后就饱和了。

每个城镇为了强化治安,对外地人的最多停留次数有严格的规定。

请你帮小T 设计一个收益最大的巡回方案,即从家乡出发,在经过的每个城镇停留,最后回到家乡的旅行方案。

你的程序只需输出最大收益,以及最优方案是否唯一。

方案并不包括路线的细节,方案相同的标准是选择经过并停留的城镇是否相同。因为取消巡回也是一种方案,因此最大收益不会是负数。

小T 在家乡净收益是零,因为在家乡是本地人,家乡对小 T当然没有停留次数的限制。

【Input】

输入的第一行是一个正整数n(5<=n<=100000),表示城镇数目。城镇以1到n的数命名。

小T 的家乡命名为1。

第二行和第三行都包含以空格隔开的n-1个整数,第二行的第i个数表示在城镇i+1停留的净收益。第三行的第i个数表示城镇i+1规定的最大停留次数。

所有的最大停留次数都不小于2。

接下来的n-1行每行两个1到n的正整数x,y,之间以一个空格隔开,表示x,y之间有一条不经过其它城镇的双向道路。

输入数据保证所有城镇是连通的。 

【Output】

输出有两行,第一行包含一个自然数,表示巡回旅行的最大收益。

如果该方案唯一,在第二行输出“solution is unique”,否则在第二行输出“solution is not unique”。

【Sample Input】

  9
  -3 -4 2 4 -2 3 4 6
  4 4 2 2 2 2 2 2
  1 2
  1 3
  1 4
  2 5
  2 6
  3 7
  4 8
  4 9

【Sample Output】

  9

   solution is unique

 

【Solution】
这个题目乍一看是个图诶
但是是DAG
就相当于一棵树
那么考虑到状态不同决策不同
很容易联想到动态规划

对于第一个问题
  关键是考虑每一个点的访问限制
  假设对于当前点i的限制是cnt[i]
  那么最多只能访问其cnt[i] - 1棵子树
  因为要留出一次机会回溯到出发点
  对于家乡的话就初始化成最大值,无限制访问

对于第二个问题
  路径唯一或不唯一
  唯一的情况不用解释
  不唯一的情况: 

  • 存在一种最优方案使得经过的某个点 u 满足dp[u]?=0 。
  • 存在在一种最优方案使得经过的某个点 u 存在至少 cnt[u]? 个儿子, 且第 cnt[u]? 大收益非负的儿子不唯一。(权值相同)

重点:1.给所有的子树进行排序,取前cnt[i] - 1棵子树

   2.排序后取到负值后结束

技术图片技术图片
//YouXam
#include 
#include 
#include 
using namespace std;
const int N = 100000;
struct edge {
    int i, next;
} edges[2 * N + 5];
int head[N + 5], tot, n, w[N + 5], limit[N + 5], dp[N + 5], ansn[N + 5],sonn[N + 5];
void add(int u, int v) {
    edges[++tot].i = v;
    edges[tot].next = head[u];
    head[u] = tot;
}
bool cmp(int a, int b) { return dp[a] > dp[b]; }
void dfs(int root, int f) {
    dp[root] = w[root];
    int sOntot= 0, sOni= 0;
    for (int i = head[root]; i; i = edges[i].next)
        if (edges[i].i != f) dfs(edges[i].i, root);
    for (int i = head[root]; i; i = edges[i].next)
        if (edges[i].i != f) sonn[++sontot] = edges[i].i;
    sort(sonn + 1, sonn + 1 + sontot, cmp);
    while (soni 1, sontot) && dp[sonn[soni + 1]] >= 0)
        dp[root] += dp[sonn[++soni]], ansn[root] |= ansn[sonn[soni]];//按位或
    if (soni  0 && dp[sonn[soni]] == dp[sonn[soni + 1]] || dp[sonn[soni]] == 0 && soni > 0 && soni <= limit[root] - 1)//两种情况,注意边界
        ansn[root] = 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i "%d", &w[i + 1]);
    for (int i = 1; i "%d", &limit[i + 1]);
    for (int i = 1; i ) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    limit[1] = n + 1;//在家乡没有停留限制
    dfs(1, 0);
    printf("%d\n%s", dp[1], ansn[1] ? "solution is not unique" : "solution is unique");
    return 0;
}
Code

JSOI2015 Salesman(树型DP)


推荐阅读
  • 在 POJ1651 的乘法谜题挑战中,如果选手按相反顺序选择卡片,即先选 50,再选 20,最后选 1,则最终得分会有所不同。题目要求输入的第一行包含... 改写后的摘要:在 POJ1651 的乘法谜题挑战中,如果选手按照逆序选取卡片,例如依次选择 50、20 和 1,最终的得分将发生变化。题目首先要求输入的第一行包括... ... [详细]
  • 在Android平台上,视频监控系统的优化与应用具有重要意义。尽管已有相关示例(如http:www.open-open.comlibviewopen1346400423609.html)展示了基本的监控功能实现,但若要提升系统的稳定性和性能,仍需进行深入研究和优化。本文探讨了如何通过改进算法、优化网络传输和增强用户界面来提高Android视频监控系统的整体效能,以满足更复杂的应用需求。 ... [详细]
  • AngularJS 进阶指南:第三部分深入解析
    在本文中,我们将深入探讨 AngularJS 的指令模型,特别是 `ng-model` 指令。`ng-model` 指令用于将 HTML 元素与应用程序数据进行双向绑定,支持多种数据类型验证,如数字、电子邮件地址和必填项检查。此外,我们还将介绍如何利用该指令优化表单验证和数据处理流程,提升开发效率和用户体验。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 在探讨Hibernate框架的高级特性时,缓存机制和懒加载策略是提升数据操作效率的关键要素。缓存策略能够显著减少数据库访问次数,从而提高应用性能,特别是在处理频繁访问的数据时。Hibernate提供了多层次的缓存支持,包括一级缓存和二级缓存,以满足不同场景下的需求。懒加载策略则通过按需加载关联对象,进一步优化了资源利用和响应时间。本文将深入分析这些机制的实现原理及其最佳实践。 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • 在 CentOS 6.5 系统上部署 VNC 服务器的详细步骤与配置指南
    在 CentOS 6.5 系统上部署 VNC 服务器时,首先需要确认 VNC 服务是否已安装。通常情况下,VNC 服务默认未安装。可以通过运行特定的查询命令来检查其安装状态。如果查询结果为空,则表明 VNC 服务尚未安装,需进行手动安装。此外,建议在安装前确保系统的软件包管理器已更新至最新版本,以避免兼容性问题。 ... [详细]
  • 在数字图像处理中,Photoshop 的直方图是一个重要的工具,它能够精确地反映图像中不同亮度级别的分布情况。通过分析直方图,用户可以深入了解图像的曝光、对比度和色调范围,从而进行更精细的调整。直方图不仅模拟了物体表面反射光线的原理,还能帮助摄影师和设计师更好地掌握图像的明暗细节,优化视觉效果。 ... [详细]
  • 本文深入探讨了Java多线程环境下的同步机制及其应用,重点介绍了`synchronized`关键字的使用方法和原理。`synchronized`关键字主要用于确保多个线程在访问共享资源时的互斥性和原子性。通过具体示例,如在一个类中使用`synchronized`修饰方法,展示了如何实现线程安全的代码块。此外,文章还讨论了`ReentrantLock`等其他同步工具的优缺点,并提供了实际应用场景中的最佳实践。 ... [详细]
  • 这是一道涉及数学计算的问题。假设步行速度为 \(a\),车速为 \(b\),总距离为 \(c\)。Teddy 的步行时间为 \(T_1\),WhereIsHeroFrom 的步行时间为 \(T_2\),总时间为 \(T\)。通过分析不同时间段内的速度变化,可以得出最优的车辆使用策略,以最小化总的旅行时间。具体来说,需要计算在不同情况下步行和乘车的时间分配,以确保整体效率最大化。 ... [详细]
  • NOIP2000的单词接龙问题与常见的成语接龙游戏有异曲同工之妙。题目要求在给定的一组单词中,从指定的起始字母开始,构建最长的“单词链”。每个单词在链中最多可出现两次。本文将详细解析该题目的解法,并分享学习过程中的心得体会。 ... [详细]
  • ### 摘要`mkdir` 命令用于在指定位置创建新的目录。其基本格式为 `mkdir [选项] 目录名称`。通过该命令,用户可以在文件系统中创建一个或多个以指定名称命名的文件夹。执行此操作的用户需要具备相应的权限。此外,`mkdir` 还支持多种选项,如 `-p` 用于递归创建多级目录,确保路径中的所有层级都存在。掌握这些基本用法和选项,有助于提高在 Linux 系统中的文件管理效率。 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • 在众多市场调研公司中,如何选择一家值得信赖的合作伙伴至关重要。基于我在市场调查行业近二十年的经验,我将推荐几家国内知名的市场调研机构,供您参考:1. 开元研究——专注于零售报刊发行研究、媒体广告价值评估及网络营销分析等领域,以其专业性和准确性赢得了广泛认可。 ... [详细]
  • POJ3669题目解析:基于广度优先搜索的详细解答
    POJ3669(http://poj.org/problem?id=3669)是一道典型的广度优先搜索(BFS)问题。由于陨石的降落具有时间属性,导致地图状态会随时间动态变化。因此,可以利用结构体来记录每个陨石的降落时间和位置,从而有效地进行状态更新和路径搜索。 ... [详细]
author-avatar
手机用户2602903375
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有