POJ 2240---Arbitrage(Floyd的dp思想)-白红宇

POJ 2240---Arbitrage(Floyd的dp思想)

阅读量：4047 次

发布时间：2019-05-25

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

题意:

给你一些货币比如A,B,C,然后给你他们之间存在的对换关系,如A可以换0.5个B,B可以换10个C,C可以换2个A等.然后问你是否存在一种对换可以使得1个A可以换到大于1个A的钱.

分析:

首先把每个货币的单词映射成一个数字,表示该货币的编号.然后其实本题用到了类似Floyd的动态规划思想.

首先假设货币1对换货币2 比率为a,货币2对换货币3 比率为b.

那么货币1对换货币3比率为多少呢?为a*b.

现在我们希望货币能增值,所以如果货币1换货币3 有两种比率分别为0,5和0,6.那么我们明显放弃0.5那个,只需要用0.6的比率即可.所以这道题就成了求一个有向图的任意两点的最大兑换比例,不过这个比例不是相加运算了,而是相乘运算.

核心：利用floyd算法的dp思想。

#include
   
    #include
    
     #include
     #include
      
       #include
       
        #define MAX 35using namespace std;int n, m;double d[MAX][MAX];void init(){	for (int i = 0; i < n; i++)		for (int j = 0; j < n; j++)			d[i][j] = i == j ? 1.0 : 0;}void floyd(){	for (int k = 0; k < n; k++)		for (int i = 0; i < n; i++)			for (int j = 0; j < n; j++)				if (d[i][j] < d[i][k] * d[k][j])					d[i][j] = d[i][k] * d[k][j];}int main(){	int num = 0;	while (cin >> n, n)	{		map
        
         mp; for (int i = 0; i < n; i++) { string s; cin >> s; mp[s] = i; } init(); cin >> m; for (int i = 0; i < m; i++) { string s1, s2; double val; cin >> s1 >> val >> s2; d[mp[s1]][mp[s2]] = val; } floyd(); int i; for (i = 0; i < n; i++) if (d[i][i] > 1.0)break; if(i==n)printf("Case %d: No\n", ++num); else printf("Case %d: Yes\n", ++num); } system("pause");}

转载地址：http://nuyci.baihongyu.com/

你可能感兴趣的文章