首页 > 搜索 > DFS搜索 > HDU 4219-Randomization?-动态规划-[解题报告]HOJ
2015
05-23

HDU 4219-Randomization?-动态规划-[解题报告]HOJ

Randomization?

问题描述 :

Random is the real life. What we see and sense everyday are absolutely randomly happened. Randomization is the process of making something random, as the nature.
Given a tree with N nodes, to be more precisely, a tree is a graph in which each pair of nodes has and only has one path. All of the edges’ length is a random integer lies in interval [0, L] with equal probability. iSea want to know the probability to form a tree, whose edges’ length are randomly generated in the given interval, and in which the path’s length of every two nodes does not exceed S.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, L, S. Then N – 1 lines following, each line contains two integers Ai and Bi, describing an edge of the tree.

Technical Specification
1. 1 <= T <= 512
2. 1 <= N <= 64
3. 1 <= L <= 8, 1 <= S <= 512
4. 1 <= Ai, Bi <= N

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, L, S. Then N – 1 lines following, each line contains two integers Ai and Bi, describing an edge of the tree.

Technical Specification
1. 1 <= T <= 512
2. 1 <= N <= 64
3. 1 <= L <= 8, 1 <= S <= 512
4. 1 <= Ai, Bi <= N

样例输入:

3
2 3 2
1 2
4 3 4
1 2
2 3
3 4
7 4 10
1 2
2 3
4 5
2 6
4 7
4 6

样例输出:

Case 1: 0.750000
Case 2: 0.500000
Case 3: 0.624832

http://acm.hdu.edu.cn/showproblem.php?pid=4219

这道dp题,蛋疼了我一天,算是有点理解了吧,待看

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

#define SZ(v) ((int)(v).size())
const int MAXN = 65, MAXS = 520;

int t, n, l, s, a, b;
vector<int> maps[MAXN];
double dp[MAXN][MAXS], son[MAXS], tmp[MAXS], ans, e;

void dfs(int x, int p)
{
        for (int i = 0; i <= s; ++ i)
                dp[x][i] = 0.0;
        dp[x][0] = 1.0;
        for (int i = 0; i < SZ(maps[x]); ++ i)
        {
                int c = maps[x][i];
                if (c != p)
                {
                        dfs(c, x);
                        for (int j = 0; j <= s; ++ j)
                                son[j] = tmp[j] = 0.0;

                        for (int j = 0; j <= l; ++ j)
                                for (int k = 0; k <= s; ++ k)
                                        if (j + k <= s)
                                                son[j + k] += dp[c][k] * e;

                    /*  for(int i=0;i<=s;i++)
                          cout<< son[i] <<" ";
                        cout<<endl;
                        for(int i=0;i<=s;i++)
                          cout<< dp[x][i] <<" ";
                        cout<<endl;
                        cout<<endl;*/
                        for (int j = 0; j <= s; ++ j)
                        {
                                //cout<<s-j<<" :: ";
                                for (int k = 0; k <= s - j; ++ k)
                                {
                                        //cout<<max(i,j)<<endl;
                                        tmp[max(j, k)] += son[j] * dp[x][k];
                                       // cout<< max(j,k)<<" "<<tmp[max(j,k)]<<endl;
                                }
                        }
                        for (int j = 0; j <= s; ++ j)
                                dp[x][j] = tmp[j];
                       // cout<<endl;
                }
        }
}

int main()
{
        scanf("%d", &t);
        for (int m = 1; m <= t; ++ m)
        {
                scanf("%d%d%d", &n, &l, &s);
                e = 1 / (l + 1.0);
                for (int i = 1; i <= n; ++ i)
                        maps[i].clear();
                for (int i = 1; i < n; ++ i)
                {
                        scanf("%d%d", &a, &b);
                        maps[a].push_back(b);
                        maps[b].push_back(a);
                }
                dfs(1, -1);
                ans = 0.0;
                /*for(int i=1;i<=n;i++)
                {
                    for(int j=0;j<=s;j++)
                      printf("%.3lf ",dp[i][j]);
                    cout<<endl;
                }*/
                for (int i = 0; i <= s; ++ i)
                        ans += dp[1][i];
                printf("Case %d: %.6lf\n", m, ans);
        }
        return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/struggle_mind/article/details/7712946