uva 104(dp)

題意：給出了n種貨币，然後給出了每種貨币和其他n-1種貨币的匯率，問是否能有一種貨币換算情況使一種貨币能從本身1經過換算後增加0.01以上，如果有輸出最短的換算方式，否則輸出no。

題解：dp題，用f[t][i][j]儲存在第t次從貨币i換算到貨币j的最大換算出的錢，狀态轉移方程就是f[t][i][j] = max{f[t][i][j], f[t - 1][i][k] * m[k][j] },其中k是枚舉的中轉點，如果f[t][i][i] > 1.01說明成功，然後用path[t][i][j]存儲第t次換算從貨币i到j的中轉點，遞歸列印路徑。

#include <stdio.h>
#include <string.h>
const int N = 25;
int n;
double m[N][N];
double f[N][N][N];
int path[N][N][N];

void print(int t, int i, int j) {
	if (t == 1) {
		printf("%d", i);
		return;
	}
	print(t - 1, i, path[t][i][j]);
	printf(" %d", path[t][i][j]);
}

bool dp() {
	for (int t = 2; t <= n; t++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				double maxx = -1;
				int index;
				for (int k = 1; k <= n; k++)
					if (maxx < f[t - 1][i][k] * m[k][j]) {
						maxx = f[t - 1][i][k] * m[k][j];
						index = k;
					}
				f[t][i][j] = maxx;
				path[t][i][j] = index;
			}
			if (f[t][i][i] - 1.01 > 1e-9) {
				print(t, i, i);
				printf(" %d\n", i);
				return true;
			}
		}
	}
	return false;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j) {
					scanf("%lf", &m[i][j]);
					f[1][i][j] = m[i][j];
				}
		int res = dp();
		if (!res)
			printf("no arbitrage sequence exists\n");
	}
	return 0;
}