文档章节

UVA 104 - Arbitrage

aqia358
 aqia358
发布于 2014/06/04 15:24
字数 500
阅读 46
收藏 0
点赞 0
评论 0

这道题的题意是:给出n种国家的货币汇率,一定金额的某种货币经过一系列汇率变换后再换成原来货币,金额增加了,求出这样的一个变换,要求变换步数最少。

由于数据量不大,我们可以直接用动规+floyd解决,设f[p][i][j]为由i到j经过p次转换所能达到的最大汇率乘积,每循环一次p我们就扫描一遍f[p][i][i],如果有大于1的情况就直接打印结果即可。

    在记录路径时用path[p][i][j]记录第k次转换的初始位置,打印时采用递归的方式。

Sample Input

3

1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

Sample Output

1 2 1

1 2 4 1
no arbitrage sequence exists

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Arbitrage {

	public static int n;
	public static float[][][] f;
	public static int[][][] path;

	public static void floyd() {
		int p, i, j, k;
		p = i = j = k = 0;
		for (p = 1; p < n; p++) {
			for (i = 0; i < n; ++i)
				for (j = 0; j < n; ++j)
					for (k = 0; k < n; ++k) {//找到f(p-1)到f(p)转换的最大值保存下来,同时保存转换路径
						if (f[p - 1][i][k] * f[0][k][j] > f[p][i][j]) {
							f[p][i][j] = f[p - 1][i][k] * f[0][k][j];
							path[p][i][j] = k;
						}
					}
			for (int m = 0; m < n; ++m) {
				if (f[p][m][m] > 1) {
					// System.out.println("find some thing");
					print(m, m, p);
					System.out.println();
				}
			}
		}
	}

	public static void print(int i, int j, int p) {
		if (p == 0) {
			System.out.print(i+" ");//打印起点
			System.out.print(j+" ");//打印起点后打印途径点
		} else {
			print(i, path[p][i][j], p - 1);//先遍历到起点再开始打印
			System.out.print(j+" ");//打印途径点
		}
	}

	public static void main(String[] args) {
		try {
			FileInputStream fis = new FileInputStream(new File("D:/a.txt"));
			StreamTokenizer st = new StreamTokenizer(new BufferedReader(
					new InputStreamReader(fis)));
			while (st.nextToken() != StreamTokenizer.TT_EOF) {
				System.out.println("-------");
				n = (int) st.nval;
				f = new float[n][n][n];
				path = new int[n][n][n];
				for (int i = 0; i < n; ++i) {
					for (int j = 0; j < n; ++j) {
						if (i == j)
							f[0][i][j] = 1;
						else {
							st.nextToken();
							f[0][i][j] = (float) st.nval;
						}
					}
				}
				floyd();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}




© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
POJ 2240-Arbitrage(SPFA判断正环-邻接矩阵+邻接表)

Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppo......

Akatsuki__Itachi ⋅ 01/20 ⋅ 0

[笔记]Implied Risk Neutral Distribution

1. 前言 最近关注了一个非常不错的微信公众号,叫做伽玛交易员(微信号:gammatrader)。微信号的主人是一位非常出色的期权交易员,之前一直在香港从事期权交易。网上有一篇关于他的小传htt...

Clever Liu ⋅ 2016/07/19 ⋅ 0

robocup uva老版本代码改写

老代码Uva或者二进制不能连接,解决问题看这里:http://sourceforge.net/forum/forum.php?threadid=2055268&forumid=76439 针对这个问题的解答,我摘录到这里 Almost all past binaries and...

枫言风语 ⋅ 2012/09/01 ⋅ 0

10055 - Hashmat the Brave Warrior

第一次玩UVa, 提交了N次都没有AC, 实在不行了, 网上找了答案, 发现是自己把问题想复杂了. 或者说是没有经验, 未能发现其中的陷阱, 导致总是 runtime error. 主要注意两点: 1. or vice versa....

sailtseng ⋅ 2013/06/03 ⋅ 0

ACM在线题库

现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专...

凡平 ⋅ 2011/10/09 ⋅ 0

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 (题解)

比赛链接:第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 A:斐波那契变形 规律:当前项 = 前面所有项之和 + 1,其实打表以后会发现是2^N,懒得改代码了直接交了。 #include using names...

zscdst ⋅ 03/29 ⋅ 0

聚集地收录

开源中国 github nocow codeforce topcoder uva poj acminfo ibm csdn wiki YGOPRO w-ai.org 白丝魔理沙 avbot hdu zoj 黑客与极客 edx MOOC Cool shell 推酷 wuyun LEECODE 九度OJ ICPC ACN......

面码 ⋅ 2014/05/15 ⋅ 0

RoboCup 2D在Ubuntu 12.04下的仿真平台环境搭建和上场全过程

本文主要讲述:从fresh的新鲜出炉的Ubuntu 12.04,一步一步到RoboCup 2D仿真平台的成功搭建,再到上场test搭建成功的全部过程。 本文参考官方教程:请点击这里 和一篇对我帮助很大的文章:请...

枫言风语 ⋅ 2012/09/01 ⋅ 0

10474 - Where is the Marble?

题意: 读入一行2个数字 N 和 Q, N 表示接下来的 N 行数字为 marbles, Q 表示 N 行数字之后的 Q 行数字为 query. 要求把 N 行 marbles 从小到大排序, 然后输出每个 Q 在 marbles 中的位置. 思...

sailtseng ⋅ 2013/07/23 ⋅ 0

GDB调试打印STL对象

其实就gdbstlutils是定义的一些语句,就如同shell中的.bashrc一样,可以在启动gdb后把它source进取,也可以重命名到系统目录或者当前路径 .gdbinit 这样gdb在启动的时候就加载了这些所谓的语...

彼得 ⋅ 2014/03/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

懒惰根本就不存在

简评:芝加哥大学心理学教授,懒惰根本就不存在。(本文表面讲行为心理学实则讲教育) 金句:以好奇而不是判断来回应一个人的无效行为,是非常有帮助的。 本文「我」代表原作者 E Price。 自...

极光推送 ⋅ 29分钟前 ⋅ 0

Excel提取单元格中最后一个“.”后面的数据

java.lang.String ----- String =TRIM((MID(SUBSTITUTE(B2,".",REPT(" ",99)),(LEN(B2)-LEN(SUBSTITUTE(B2,".","")))*99,99)))...

klog ⋅ 31分钟前 ⋅ 0

mac远程桌面

下载安装remote-desktop-mac Mac beta 客户端 mac通过远程桌面访问windows服务器。

亚林瓜子 ⋅ 35分钟前 ⋅ 0

firrtl

动手---sbt(2)之后,再回头看 chisel第一个实验,根据 https://github.com/freechipsproject/firrtl 发现firrtl没有执行sbt assembly命令,重新执行这个命令,结果成功。如下图: joe@joe-As...

whoisliang ⋅ 39分钟前 ⋅ 0

NIO

一、通道(Channel):用于源节点与目标节点的连接。在 Java NIO 中负责缓冲区中数据的传输。Channel 本身不存储数据,因此需要配合缓冲区进行传输。 二、通道的主要实现类 java.nio.channel...

stars永恒 ⋅ 40分钟前 ⋅ 0

Android悬浮窗的实现

0. 前言   现在很多应用都使用到悬浮窗,例如微信在视频的时候,点击Home键,视频小窗口仍然会在屏幕上显示。这个功能在很多情况下都非常有用。那么今天我们就来实现一下Android悬浮窗,以...

猴亮屏 ⋅ 40分钟前 ⋅ 0

日志采集中的关键技术分析

概述 日志从最初面向人类演变到现在的面向机器发生了巨大的变化。最初的日志主要的消费者是软件工程师,他们通过读取日志来排查问题,如今,大量机器日夜处理日志数据以生成可读性的报告以此...

tqyin ⋅ 41分钟前 ⋅ 0

使用Navicat将数据导出为text文本 然后再导入

将数据导出为text文本效率很高 1. 准备工作 1.1 准备表结构 1.2 目标库 执行生成表结构sql 2.将表数据导出为text文本 生成的text文本 3. 目标库 导入text 4.效果...

Lucky_Me ⋅ 47分钟前 ⋅ 0

IntelliJ IDEA 乱码解决方案 (项目代码、控制台等)

文章介绍了idea下,项目乱码、控制台乱码及运行tomcat控制台乱码的解决方案,文章链接:https://www.cnblogs.com/vhua/p/idea_1.html

Funcy1122 ⋅ 50分钟前 ⋅ 0

IDEA使用sonarLint

一、IDEA如何安装SonarLint插件 1.打开 Idea 2.点击【File】 3.点击【Settings】 4.点击【Plugins】 5.在搜索栏中输入“sonarlint”关键字 6.点击【Install】进行安装 7.重启Idea 二、IDEA如...

开源中国成都区源花 ⋅ 55分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部