| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
记忆化搜索飘过、、、#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator