概率DP POJ3071 正求概率

如果用按位操作符就一定要加括号。。
除非你能都搞懂…
还有啊

这题get到新知识 二分式比赛的方法

题目链接

//MADE BY Y_is_sunshine;
//#include 
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define MAXN 1005
const int mod = 1e9 + 7;
const double PI = acos(-1);
using namespace std;
double dp[10][1 << 8 + 5];
double d[1 << 8 + 5][1 << 8 + 5];
int main(void)
{
    freopen("data.txt", "r", stdin);
    int N;
    while (cin >> N) {
        if (N == -1)
            break;
        int tot = 1 << N;
        for (int i = 0; i < tot; i++) {
            for (int j = 0; j < tot; j++)
                scanf("%lf", &d[i][j]);
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= tot; i++)
            dp[0][i] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < tot; j++) {
                for (int k = 0; k < tot; k++) {
                    if (j >> (i - 1) == (k >> (i - 1) ^ 1))
                        dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * d[j][k];
                }
            }
        }
        int flag = 0;
        double max_ans = 0;
        for (int i = 0; i <= tot; i++) {
            if (dp[N][i] > max_ans)
                max_ans = dp[N][i], flag = i;
        }
        cout << flag + 1 << endl;
    }
    freopen("CON", "r", stdin);
    system("pause");
    return 0;
}