UVa 104 - Arbitrage（Floyd动态规划）

题目来源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40

Arbitrage

Background

The use of computers in the finance industry has been marked with controversy lately as programmed trading -- designed to take advantage of extremely small fluctuations in prices -- has been outlawed at many Wall Street firms. The ethics of computer programming is a fledgling field with many thorny issues.

The Problem

Arbitrage is the trading of one currency for another with the hopes of taking advantage of small differences in conversion rates among several currencies in order to achieve a profit. For example, if $1.00 in U.S. currency buys 0.7 British pounds currency, £1 in British currency buys 9.5 French francs, and 1 French franc buys 0.16 in U.S. dollars, then an arbitrage trader can start with $1.00 and earn dollars thus earning a profit of 6.4 percent.

You will write a program that determines whether a sequence of currency exchanges can yield a profit as described above.

To result in successful arbitrage, a sequence of exchanges must begin and end with the same currency, but any starting currency may be considered.

The Input

The input file consists of one or more conversion tables. You must solve the arbitrage problem for each of the tables in the input file.

Each table is preceded by an integer n on a line by itself giving the dimensions of the table. The maximum dimension is 20; the minimum dimension is 2.

The table then follows in row major order but with the diagonal elements of the table missing (these are assumed to have value 1.0). Thus the first row of the table represents the conversion rates between country 1 and n-1 other countries, i.e., the amount of currency of country i ( ) that can be purchased with one unit of the currency of country 1.

Thus each table consists of n+1 lines in the input file: 1 line containing n and n lines representing the conversion table.

The Output

For each table in the input file you must determine whether a sequence of exchanges exists that results in a profit of more than 1 percent (0.01). If a sequence exists you must print the sequence of exchanges that results in a profit. If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.

Because the IRS (United States Internal Revenue Service) notices lengthy transaction sequences, all profiting sequences must consist of n or fewer transactions where n is the dimension of the table giving conversion rates. The sequence 1 2 1 represents two conversions.

If a profiting sequence exists you must print the sequence of exchanges that results in a profit. The sequence is printed as a sequence of integers with the integer i representing the line of the conversion table (country i). The first integer in the sequence is the country from which the profiting sequence starts. This integer also ends the sequence.

If no profiting sequence of n or fewer transactions exists, then the line

no arbitrage sequence exists

should be printed.

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
解题思路：
给出n种国家的货币汇率，一定金额的某种货币经过一系列汇率变换后再换成原来货币，金额增加了，求出这样的一个变换，要求变换步数最少。

Floyd变形，关于Floyd动态规划的理解。

状态转移方程：
f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])
f[k][i][j]表示只经过前k个点(包括k)，从i到j的最小值。当k从1到n时，就是从i到j的最小值。我们熟悉的用二维数组的写法实际上是对空间的一种压缩。
解释一下：
计算只经过前k个点，从i到j的最小值时，有两种情况需要考虑：经过第k个点和不经过第k个点。经过第k个点则距离应是从i到k的最小值和从k到j的最小值，两个最小值的路径都必须只经过前k-1个点（为什么是k-1而不是k，事实上他们两数值相同，因为起点和终点已经有第k个点，只是在dp的过程中先产生k-1，f[k][i][k]和f[k][k][j]有可能比f[k][i][j]的值晚计算出，就不能在计算f[k][i][j]时用到这两个值）。不经过k的点则距离与只经过前k-1个点时一样。

参考代码：

 #include <cstdio>

 #include <cstring>

 #define N 25

 double dp[N][N][N],p[N][N][N];

 int n;

 void print_path(int i ,int j , int s)

 {

     if(s==)

     {

         printf("%d",i);

         return ;

     }

     print_path(i, p[i][j][s] ,s-);

     printf(" %d",j);

     return ;

 }

 void DP()

 {

     int s,m;

     for(s=; s<=n; s++)

     {

         for(int k=; k<=n; k++)

             for(int i=; i<=n; i++)

                 for(int j=; j<=n; j++)

                     if( dp[i][j][s] < dp[i][k][s-]*dp[k][j][])

                     {

                         dp[i][j][s]=dp[i][k][s-]*dp[k][j][];

                         p[i][j][s]=k;

                     }

         int i;

         for(i=; i<=n; i++)

             if(dp[i][i][s]>1.01)

             {

                 m=i ;

                 break;

             }

         if(i<=n)

             break;

     }

     if(s>n)

         printf("no arbitrage sequence exists");

     else

         print_path(m , m , s);

     printf("\n");

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         memset(dp,,sizeof(dp));

         memset(p,,sizeof(p));

         for(int i=; i<=n; i++)

             for(int j=; j<=n; j++)

             {

                 if(i==j) dp[i][j][]=;

                 else

                     scanf("%lf",&dp[i][j][]);

                 p[i][j][]=j;

             }

         DP();

     }

     return ;

 }

具体分析推荐博客：http://www.cnblogs.com/scau20110726/archive/2012/12/26/2834674.html

巴特西