40分求助
查看原帖
40分求助
172212
herolxl楼主2022/2/24 15:57
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;

const int N = 1e3 + 100;
double a[N][N];
double dp[N][20];
int n, m = 1;


int max(int x, int y) {
	return x > y ? x : y;
}

void emmm(int c, int b) {
	int s = c >> (b - 1), ss = 1;
	s = s ^ 1;
	s <<= (b - 1);
	for (int i = 1; i < b; ++i) {
		ss *= 2;
	}
	ss += s;
	for (int i = s; i < ss; ++i) {
		dp[c][b] += dp[c][b - 1] * dp[i][b - 1] * a[c][i];
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		m *= 2;
	}
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
			a[i][j] /= 100;
		}
	}
	for (int i = 0; i < m; ++i) {
		dp[i][1] = a[i][i ^ 1];
	}
	for (int j = 2; j <= n; ++j) {
		for (int i = 0; i < m; ++i) {
			emmm(i, j);
		}
	}
	int ans = 0;
	for (int i = 1; i < m; ++i) {
		ans = dp[ans][n] >= dp[i][n] ? ans : n;
	}
	cout << ans + 1;
}
/*
  2
  0 10 50 50
  90 0 10 10
  50 90 0 50
  50 90 50 0
*/
2022/2/24 15:57
加载中...