首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。