Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

记忆化搜索飘过、、、

Posted by Moon_1st at 2011-03-22 19:55:03 on Problem 3071 and last updated at 2011-03-22 19:55:26
#include <cstdio>
#include <cstring>

const int N = 130;

int n;
double w[N][N], f[N][N][N];

void Dp_dfs(int l, int r, int k)
{
    int i, mid = (l+r)>>1;
    double tmp, sum;
    if(f[l][r][k] >= 0.0)  return;
    if(l+1 == r)
    {
        if(k == l)  f[l][r][k] = w[l][r];
        else  f[l][r][k] = w[r][l];
        return;
    }
    else
    {
        if(k <= mid)
        {
            Dp_dfs(l, mid, k);
            tmp = f[l][mid][k];
            sum = 0.0;
            for(i = k+1; i <= r; i++)
            {
                Dp_dfs(mid+1, r, i);
                sum += tmp*f[mid+1][r][i]*w[k][i];
            }
            f[l][r][k] = sum;
        }
        else
        {
            Dp_dfs(mid+1, r, k);
            tmp = f[mid+1][r][k];
            sum = 0.0;
            for(i = l; i <= mid; i++)
            {
                Dp_dfs(l, mid, i);
                sum += tmp*f[l][mid][i]*w[k][i];
            }
            f[l][r][k] = sum;
        }
    }
}

int main()
{
    int i, j, k, ans;
    double p;
    while(scanf("%d", &n) != EOF)
    {
        if(n == -1)  break;
        n = 1<<n;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%lf", &w[i][j]);
        for(i = 1; i <= n; i++)
            for(j = i; j <= n; j++)
                for(k = i; k <= j; k++)
                    f[i][j][k] = -1.0;
        ans = 0;
        p = 0.0;
        for(i = 1; i <= n; i++)
        {
            Dp_dfs(1, n, i);
            if(f[1][n][i] > p)
            {
                p = f[1][n][i];
                ans = i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator