XTUOJ 1252 Defense Tower 贪心_weixin_30296405的博客-程序员ITS203

技术标签: php  

题目链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1252

思路:考虑每条边对玩家的伤害

         假设连接的节点是u,v,破坏力是p[u]和p[v]

         假设p[u]>p[v]

         现在考虑u,v的删除顺序,如果先删u,这条边对玩家的伤害,是p[v],先删v,伤害是p[u]

         所以显然对于每条边,我们都要先删权值大的,才能最好

         怎么样才能对于每条边先删最大的呢,那就按照权值递减删就好了

         所以 ret=Σ(min(p[u],p[v]))

        复杂度O(n)

#include <cstdio>
using namespace std;
const int N=1e5+5;
int p[N];
int main(){
   int n;
   while(~scanf("%d",&n)){
    for(int i=1;i<=n;++i)
      scanf("%d",&p[i]);
    int ret=0;
    for(int i=1;i<n;++i){
      int u,v;
      scanf("%d%d",&u,&v);
      ret+=min(p[u],p[v]);
    }
    printf("%d\n",ret);
   }
   return 0;
}
View Code

 

转载于:https://www.cnblogs.com/shuguangzw/p/5585781.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30296405/article/details/99084700

智能推荐

构建express_15分钟内在Express中构建简单身份验证_culiu9261的博客-程序员ITS203

构建expressBuilding web pages with user authentication can be a huge pain. You typically need to set up some sort of database to manage users even if you're not using the database for anything else. You...

网格布局display: grid;_加油,铁子!的博客-程序员ITS203_display grid

什么是网格布局是一种强大的CSS布局方案,它将网页划分成一个个网格,可以任意组合的网格(类似excel)网格布局是CSS3的布局系统与弹性布局类似网格可以理解成是二维布局(弹性布局是一维的)可以使用align-item justify-content等属性IE11部分支持display:grid 设置该元素为网格容器display: grid;grid-template-columns: 列宽&lt;!DOCTYPE html&gt...

C# 多线程加锁简单示例_ou.cs的博客-程序员ITS203_c# 方法加锁

private void button8_Click(object sender, EventArgs e) { //for (int i = 0; i &lt; 5; i++) //{ // int k = i; // Thread.Sleep(5); // Task.Run(() =&gt; // { ...

ITSM常见问题之:自动指派工单给对应的技术员的三种简单方法_ManageEngine卓豪的博客-程序员ITS203

假设在某个月末,发工资的员工无法登录到工资支付应用程序,为了解决这个问题,他向IT帮助台发送了一封电子邮件,即创建了一个工单。不巧的是,这时服务台协调员并不在公司,于是工单一直处于未指派状态,直到服务台管理员将工单指派给相关技术员。同时,没有收到工资的用户逐渐失去耐心,不断给服务台团队打电话、发邮件,导致了出现了更多的工单。如果,在帮助台中创建一个工单后,能够自动指派相应的技术员岂不很好吗?ServiceDesk Plus可以帮您实现——按照以下三种方式自动将工单指派到正确的技术员,基于类别的技术员指派

随便推点

32位寄存器用法介绍_你回到了你的家的博客-程序员ITS203_32位寄存器

一、寄存器介绍32位CPU所含有的寄存器有:8个32位通用寄存器,其中包含4个数据寄存器(EAX、EBX、ECX、EDX)、2个变址寄存器(ESI和EDI)和2个指针寄存器(ESP和EBP)6个段寄存器(ES、CS、SS、DS、FS、GS)1个指令指针寄存器(EIP)1个标志寄存器(EFLAGS)二、通用寄存器每个寄存器都可作为一个32位值或两个16位值来寻址使用。某些16位的寄存器能够按照8位值寻址使用。EAX的低16位称为AX,AX的高8位称为AH,低8位称为AL。321

ORA-16014: log 3 sequence# 1 not archived, no available destinations_喝醉酒的小白的博客-程序员ITS203_ora16014

问题原因归档权限路径不正确解决方案方案1更改路径方案2修改权限

Android Java、Kotlin 混编配置_热爱学习○的博客-程序员ITS203_android kotlin混编

1、在原来的项目app 目录下build·gradle 新增apply plugin: 'kotlin-android-extensions'apply plugin: 'kotlin-android'2、配置项目下的build·gradlebuildscript{***ext.kotlin_version = '1.4.20'dependencies {classpath "org.jetbrains.kotlin:kotlin-gradle-plugin:$ko.._1671465600

最新Reveal安装与使用,可以查看任意AppUI布局。_weixin_30701521的博客-程序员ITS203

  最近在看iOS逆向的资料,发现了调试UI的工具--Reveal,发现这在实际开发中也是很有用处。当我们需要参照其他App界面布局的时候,使用这个工具可以看他的布局情况。不过这需要手机越狱才行。如果没有越狱的话,只能调试自己的App,有同学会说,如果是自己的App,那我用自带就够了,其实Reveal有个比Xcode自带的更有用的功能。Reveal提供一个可以即时改布局属性的功能,即我不...

推荐文章

热门文章

相关标签