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