洛谷p1769 DP（线段树思想）

这题乍一看很吓人，实则当你去手画一下比赛过程的时候就可以知道了，假设总人数有8人，1， 2 ， 3 ， 4 ， 5 ， 6 ，7 ，8.
题目说了每一轮都是按编号顺序从小到大去比赛的那么第一轮就是(1,2),(3,4),(5,6),(7,8).这么个比赛顺序，第二轮就是(1,2)的胜利者去比(3,4)的胜利者（另外两个同理）。这个比赛的过程在我刚刚接触这个题的时候我想的是线段树的过程，但是是一个十分完美的区间划分，线段树可能会有(1,3)区间去分开变成(1,2)和（3)的情况，但是这里不会。利用线段树的这个过程我们就可以十分完美的去模拟出这个比赛的过程。接下来考虑我们要怎么得到答案，我先说我一开始想的错误的想法，我最初为了避免小数运算，选择了把胜率当做权值去做，90%概率我就拿90分，然后去计算每个人获胜的总权值去比较大小，但是算权值的时候我用的也是加法，没去想乘法，所以一顿瞎鸡儿操作30分。。。。。
（暴躁改几次还是没用选择打开了题解233333）正确的应该是这样子的我们和线段树一样f[i]，i这个节点就代表了一个区间范围[L,R],然后我们在开一维度j表示这个区间内的胜者。f[i][j]的值就代表了j这个人在这个区间获胜的概率。要怎么算呢？首先j这个人是在左边区间来的还是右边区间来的我们可以知道，我们按他在左边儿子（区间）来的，（在右边的同理）。那么这个j节点就是在[L , mid]的区间的胜者，我们用他这个节点是这个区间的胜者的概率f[i * 2][j]去与右区间的每一个胜者获胜的概率去乘上j打赢他们的概率
f[i][j] = sum(f[i*2][j] * f[i * 2 + 1][k]),k就代表了右边区间的所有可能获胜的人。这个式子其实就是一个人在这个区间获胜是概率是在原本所在区间获胜的概率在去分别乘上要赢另一个区间那个获胜的人的概率 在乘上另一个区间那个获胜的人要在她所在原本区间要获胜的概率，有点小饶，在多看两遍。
这样就做完收工了，最后统计[1,R]区间每个人的胜率去得答案就好了

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<time.h>
#include<string>
#include<cmath>
#include <ctime>
#include<bitset>
#include <cctype>
#define debug cout<<"*********degug**********";
#define int long long
#define RE register
#define yn yn_
using namespace std;
const long long max_ = 1500 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
int quick_pow(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1)	res = res * x;
		x = x * x ;
		n >>= 1;//相当于n=n/2.详情请参考位移运算符。
	}
	return res;
}
int n, stander; double f[max_ * 4][max_], nodee[max_][max_];
void update(int node, int L, int R) {
	if (L == R) {
		f[node][L] = 1.0;
		return;
	}
	int mid = (L + R) / 2,L_tree = node * 2 , R_tree = node * 2 + 1;
	update(L_tree, L, mid); update(R_tree, mid + 1, R);
	for (int i = L; i <= mid; i++) {
		double t = 0.0;
		for (int j = mid + 1; j <= R; j++) {
			t =t +  f[R_tree][j] * nodee[i][j] * f[L_tree][i];
		}
		f[node][i] = t ;
	// printf("[%d,%d]的%d取得胜利的分数:%d\n", L, R, i, f[node][i]);
	}
	for (int i = mid + 1; i <= R; i++) {
		double t = 0.0;
		for (int j = L; j <= mid; j++) {
			t += f[L_tree][j] * nodee[i][j] * f[R_tree][i];
		}
		f[node][i] = t ;
		//printf("[%d,%d]的%d取得胜利的分数:%d\n", L, R, i, f[node][i]);
	}
}

signed main() {
	n = read();
	stander = quick_pow(2, n);
	for (int i = 1; i <= stander; i++) {
		for (int j = 1; j <= stander; j++) {
			int t = read();
			nodee[i][j] = t / 100.0;
			//if (i != j && nodee[i][j] == 0)nodee[i][j] = -inf;
		}
	}
	update(1, 1, stander);
	double ansvalue = 0; int ans = 122345;
	for (int i = 1; i <= stander; i++) {
		if (f[1][i] > ansvalue) {
			ansvalue = f[1][i];
			ans = i;
		}
		else {
			if (f[1][i] == ansvalue && ans > i)ans = i;
		}
	}cout << ans;
	return 0;
}