首页 > 代码库 > UVA 104 Arbitrage

UVA 104 Arbitrage

动态规划类似FLOYD dp[i][j][k] 表示第i个点经过K次到达j点能获得的最大利润

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 25double G[MAXN][MAXN];double dp[MAXN][MAXN][MAXN];int fa[MAXN][MAXN][MAXN];int N;int cnt,ans;void init(){    memset(dp,0,sizeof(dp));    memset(fa,0,sizeof(fa));    for (int i = 1; i <= N; i++)    {        dp[i][i][1] = 1.0;        for (int j = 1; j <= N; j++)        {            fa[i][j][1] = i;            if (i == j) continue;            scanf("%lf",&dp[i][j][1]);        }    }}bool judge(){    for (int k = 2; k <= N; k++)        for (int i = 1; i <= N; i++)        if (dp[i][i][k] > 1.01)    {        ans = i;        cnt = k;       //8 printf("%d %d\n",ans,cnt);        return true;    }    return false;}void output(int x,int y,int cnt){    if (cnt == 0)  {printf("%d",x);return ;}    //printf("%d %d %d %d\n",x,y,cnt,fa[x][y][cnt]);    output(x,fa[x][y][cnt],cnt - 1);    printf(" %d",y);}int main()//节点i通过K次转换到达节点j能拿到的钱{   // freopen("sample.txt","r",stdin);    while (scanf("%d",&N) != EOF)    {        init();        for (int k = 2; k <= N; k++)          for (int i = 1; i <= N; i++)            for (int j = 1; j <= N; j++)               for (int p = 1; p <= N; p++)        {            if (dp[i][j][k] < dp[i][p][k - 1] * dp[p][j][1])            {                dp[i][j][k] = dp[i][p][k - 1] * dp[p][j][1];                fa[i][j][k] = p;//在i经过K次转换到P的过程中第K 是p->j            }        }        bool found = judge();        if (!found)  puts("no arbitrage sequence exists");        else {  output(ans,ans,cnt); putchar(\n);}    }    return 0;}

 

UVA 104 Arbitrage