Over time, those coaches in BDN Collegiate Progranuning Contest split into two camps.The big danger is that, while optimists and pessimists battle it out, the environment of this area becomes ever more divided between universities with outstanding student resources surrounded by a vast neglected group of stagnation.
Amy and Bob, as the linchpins of these two camps respectively, decided to put the end to the rival. Now both camps hold nn coders and nn tea-bringers as the last resource on hand. They will form teams in pair that each team should consist of a coder and a tea-bringer. The power of a team is regarded as the sum of powers of both members.
Now Bob hired a spy and has got some information about the plan of his rival: the power of each team which will present for the enemy camp, and the corresponding unit of reputations that Bob would gain after beating this team. Naturally, he hopes to make the best arrangement of teams in his camp for more reputations.
These two camps will have a collision soon, and their teams will fight one on one in random order. That is, we may have n!n! different situations appearing in this collision. A team would triumphantly return if it has a higher power. When two teams of the same power meet, the one led by Amy would beat the rival by a neck.
Can you calculate the maximum expected unit of reputations that Bob will gain? To make the answer be an integer, you are asked to multiply the answer by nn and we guarantee that the expected number multiplied by nn should always be an integer.
Input
The input contains five lines, and the first line is consist of an integer n n n(1 ≤ \leq ≤ n n n ≤ \leq ≤ 400).
The second line contains n n n integers a 1 a_1 a1, a 2 a_2 a2,—, a n a_n an, with − 1 0 18 -10^{18} −1018 ≤ \leq ≤ a i a_i ai ≤ \leq ≤ 1 0 18 10^{18} 1018, indicating the powers of all the teams led by Amy.
The third line contains n n n integers p 1 p_1 p1, p 2 p_2 p2,—, p n p_n pn, with 1 ≤ \leq ≤ p i p_i pi ≤ \leq ≤ 10000, indicating the corresponding units of reputations that Bob would gain if these teams led by Amy are beaten.
The fourth line contains n n n integers b 1 b_1 b1, b 2 b_2 b2,—, b n b_n bn, with − 1 0 18 -10^{18} −1018 ≤ \leq ≤ b i b_i bi ≤ \leq ≤ 1 0 18 10^{18} 1018, indicating the powers of all coders in the camp of Bob.
The last line contains n n n integers c 1 c_1 c1, c 2 c_2 c2,—, c n c_n cn, with − 1 0 18 -10^{18} −1018 ≤ \leq ≤ c i c_i ci ≤ \leq ≤ 1 0 18 10^{18} 1018, indicating the powers of all tea-bringers in the camp of Bob.
Output
Output an integer in a single line indicating the maximum expected number of wins multiplied by n n n.
样例输入
4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2
样例输出
3
这道题需要真正的 O ( n 3 ) O(n^3) O(n3)的板子才能过,也告诉我我之前的 O ( n 3 ) O(n^3) O(n3)的板子是错误的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define ll long long
#define len 500
#define INF 0x3f3f3f3f
using namespace std;
ll a[len], b[len], c[len], d[len];
bool vis[len], vis_y[len];
ll mmap[len][len];
ll slack[len], l[len];
ll wx[len], wy[len], pre[len];
int n;
void Init(){
memset(a, 0, sizeof (a));
memset(b, 0, sizeof (b));
memset(c, 0, sizeof (c));
memset(d, 0, sizeof (d));
memset(vis, false, sizeof (vis));
memset(mmap, 0, sizeof (mmap));
memset(slack, 0, sizeof (slack));
memset(wx, 0, sizeof (wx));
memset(wy, 0, sizeof (wy));
memset(l, 0, sizeof (l));
}
void bfs(int k)
{
int px,py=0,yy=0,d;
memset(pre,0,sizeof (pre));
memset(slack,INF,sizeof (slack));
l[py]=k;
do
{
px=l[py],d=INF,vis[py]=true;
for(int i=1;i<=n;i++)
if(!vis[i])
{
if(slack[i]>wx[px]+wy[i]-mmap[px][i])
slack[i]=wx[px]+wy[i]-mmap[px][i],pre[i]=py;
if(slack[i]<d) d=slack[i],yy=i;
}
for(int i=0;i<=n;i++)
if(vis[i]) wx[l[i]]-=d,wy[i]+=d;
else slack[i]-=d;
py=yy;
}while(l[py]!=0);
while(py) l[py]=l[pre[py]],py=pre[py];
}
ll km()
{
memset(wx,0,sizeof (wx));
memset(wy,0,sizeof (wy));
memset(l,0,sizeof (l));
for(int i=1;i<=n;i++)
memset(vis,0,sizeof (vis)),bfs(i);
ll ans = 0;
for (int i=1; i<=n; i++) ans += mmap[l[i]][i];
return ans;
}
int main(){
Init();
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
for (int i=1; i<=n; i++) scanf("%lld", &b[i]);
for (int i=1; i<=n; i++) scanf("%lld", &c[i]);
for (int i=1; i<=n; i++) scanf("%lld", &d[i]);
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
for (int k=1; k<=n; k++){
if (c[i] + d[j] > a[k]) mmap[i][j] += b[k];
}
}
}
// for (int i=1; i<=n; i++){
// for (int j=1; j<=n; j++){
// printf("%d ", mmap[i][j]);
// }
// printf("\n");
// }
ll ans = km();
printf("%lld\n", ans);
return 0;
}
文章浏览阅读3.2k次。看了DL4CV的第三卷的15章faster rcnn之后,收获很多,特此做一下记录一.RCNNRCNN一共分为四步:step1:输入图片step2:采用selective search的方法获取潜在的roi,一共提取了2000个潜在roi,然后放入conv当中进行训练step3:使用迁移学习【用到了conv层】方法,提取step2的特征,从而获得最终的roiste...
文章浏览阅读1.4k次,点赞21次,收藏14次。HashMap是Java中广泛使用的键值对存储结构,了解其内部结构和工作原理对于编写高效的Java程序至关重要。在多线程环境中,使用能够更好地保证线程安全性。通过合理选择参数和注意事项,可以充分发挥HashMap在实际应用中的优势。通过本文的介绍,希望读者对HashMap有更深入的理解,能够更加灵活地应用于实际项目中。祝大家学习愉快!
文章浏览阅读964次,点赞14次,收藏17次。随着技术的不断发展和社会对自动驾驶技术的接受度提高,自动驾驶技术有望在未来成为现实,为我们的生活带来更多便利和安全。它连接了车辆的各个部件和系统,实现了数据的实时传输和通讯,为自动驾驶车辆的正常运行和安全性提供了基础支持。此外,CAN总线还可以用于车辆的诊断和故障排除,以确保车辆的安全和可靠性。通过CAN总线,不同的模块和系统可以共享数据并协同工作,实现了车辆的智能化和自动化。此外,CAN总线还可以用于车辆的诊断和故障排除,以确保车辆的安全和可靠性。_自动驾驶开发 can版本
文章浏览阅读354次,点赞9次,收藏9次。请注意,以上是一个简要的安装和使用教程,实际操作中可能会涉及到更多的配置和细节。确保按照Elasticsearch官方文档进行操作,以获得最准确的安装和配置指导。打开终端,运行以下命令来添加Elasticsearch的APT仓库。运行以下命令来验证Elasticsearch是否在运行。运行以下命令来启动Elasticsearch服务。运行以下命令来安装Elasticsearch。
文章浏览阅读1.2w次,点赞6次,收藏3次。1:使用npm下载://(注意 wangeditor 全部是小写字母)npm install wangeditor 122: 直接在项目模板中引用import E from 'wangeditor'13:HTML <div id="editorElem" style="text-align:left"></div> <button v-on:click="..._@wangeditor/editor-for-vue 读取data-src 定义的内容
文章浏览阅读1.6k次,点赞3次,收藏4次。安装点云PCL库时,需要额外安装5个依赖库;它们有什么作用呢?如下:Boost: 用于共享指针和多线程。Eigen: 一个标准的C++模板库用于线性代数,矩阵,向量等计算。FLANN:(Fast Approximate Nearest Neighbor Search Library), 快速最近邻逼近搜索函数库,可实现快速高效匹配。OpenNI:一个开源的框架,用于3D传感器中间件的应用开发。VTK:三维点云的可视化和渲染。计算机图形学,图像处理,可视化方面的库。..._pcl依赖库
文章浏览阅读1w次。 引用: 名称: 事项001 描述: 翻译由斯坦福大学维护的最新网络监视工具列表. http://www.slac.stanford.edu/xorg/nmtf/nmtf-tools.html 执行人: leechael 启动时间: 2006-04-24 _monitoring tool for database clients
文章浏览阅读3.9k次,点赞5次,收藏28次。论文发表年限:CVPR,2020作者:Hyunjong Park、Jongyoun Noh、Bumsub Ham论文下载地址:Learning Memory-guided Normality for Anomaly Detectiongithub地址:https://github.com/cvlab-yonsei/MNAD摘要:异常检测、无监督Motivation现有的方法没有考虑到正常行为(normal)的多样性。同时强大的CNN网络能够重构异常行为(abnormal),导致不能检测出异常行为
文章浏览阅读81次。/***description:Android HttpPost()*authour:YanEr·Gates*website:https://www.jb51.net*/package me.gogogoog;import java.io.IOException;import java.util.ArrayList;import java.util.List;import org.apache.h..._android 网络请求http案例
文章浏览阅读3.5k次。__init__()方法意义重大的原因有两个。第一个原因是在对象生命周期中初始化是最重要的一步;每个对象必须正确初始化后才能正常工作。第二个原因是__init__()参数值可以有多种形式。因为有很多种方式为__init__()提供参数值,对于对象创建有大量的用例,我们可以看看其中的几个。我们想尽可能的弄清楚,因此我们需要定义一个初始化来正确的描述问题区域。在我们接触__init__()方法之前,无..._def __init__
文章浏览阅读68次。本文介绍下SpringBoot整合Mybatis(XML配置方式)的过程。本文目录 一、什么是 MyBatis?二、整合方式三、实战四、测试一、什么是 MyBatis? MyBatis 是一款优秀的持久层框架,它支持定制化 SQL、存储过程以及高级映射。MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集。MyBatis 可以使用简单的 XML 或注解来配置和映射原生类型..._"怎么用传递参数"
文章浏览阅读2.1w次,点赞34次,收藏154次。计算机内部关于运算器的实验!(带你了解运算器是如何工作的)在线博主,及时解答~_采用一个74ls181作为alu核心,采用74ls373作为4位操作数a和4位操作数b的锁存器。