【集训DAY13】Out race【数学】【动态规划】

思路：

我们直接一层一层比，算出概率就行了

$code$

#include<iostream>
#include<cstdio>

#define re register

using namespace std;

const int MAXN = 1050;

int n, d[MAXN][MAXN];
int a[MAXN][MAXN];

double f[MAXN], q[MAXN];

int main() {
    
	scanf("%d", &n);
	int len = 1 << n;
	for(re int i = 1; i <= len; ++ i)
		for(re int j = 1; j <= len; ++ j) scanf("%d", &a[i][j]);
	for(re int i = 1; i <= len; ++ i) f[i] = 1.0, d[i][0] = 1, d[i][1] = i;
	for(re int i = 1; i <= n; ++ i) {
    
		for(re int j = 1; j <= len; j += (1 << i)) {
    
			re int k = j + (1 << i - 1);
			for(re int i1 = 1; i1 <= d[j][0]; ++ i1) {
    
				re int g = d[j][i1];
				for(re int j1 = 1; j1 <= d[k][0]; ++ j1) {
    
					re int p = d[k][j1];
					q[g] += f[p] * (a[g][p] * 1.0 / 100.0);
					q[p] += f[g] * (a[p][g] * 1.0 / 100.0);
				}
			}
			for(re int i1 = 1; i1 <= d[k][0]; ++ i1) ++ d[j][0], d[j][d[j][0]] = d[k][i1];
		}
		for(re int j = 1; j <= len; ++ j)
			f[j] = f[j] * (q[j] / ((1 << i - 1) * 1.0)), q[j] = 0.0;
	}
	re double maxx = 0.0;
	re int ans = n + 1;
	for(re int i = 1; i <= len; ++ i)
		if(f[i] > maxx) maxx = f[i], ans = i;
	printf("%d", ans);
	return 0;
}