首页 > ACM题库 > HDU-杭电 > HDU 4809-Cirno’s Present-动态规划-[解题报告]HOJ
2015
09-18

HDU 4809-Cirno’s Present-动态规划-[解题报告]HOJ

Cirno’s Present

问题描述 :

One day, three fairies, Sunny, Luna and Star visited Cirno’s house. Cirno was very happy, so she decided to give a present to them.
Cirno’s present was a tree with N nodes. Each node of the tree has an equal possibility to be owned by one of Sunny, Luna or Star. After having decided every node’s owner, Cirno cut the edges that connect different owner’s nodes, after which each of the three fairies got some connected component of nodes (possibly none).
Then each of the three fairies had to spend some magical energy repairing the components she got. Suppose she had X components containing odd number of nodes and Y components containing even number of nodes, the magical energy she would spend equals max(0, X – Y ).
Cirno would compensate for the energy they spent with some food, so she asked you the expectation of the total energy the three fairies would spend, and your task is to find out the answer.
To make it simpler, as it’s easy to prove the multiplication of the expectation and the Nth power of three makes an integer, your task is to find the remainder of the multiplication divided by 109 + 7.

输入:

There are several test cases, please process till EOF.
Each test case starts with a line containing one integer N (1 <= N <= 300). Then follows N – 1 lines, each contains two integers u and v (1 <= u, v <= N), representing an edge between node u and node v.

输出:

There are several test cases, please process till EOF.
Each test case starts with a line containing one integer N (1 <= N <= 300). Then follows N – 1 lines, each contains two integers u and v (1 <= u, v <= N), representing an edge between node u and node v.

样例输入:

1
2
1 2
3
2 1
1 3

样例输出:

3
12
51

非常值得一做的树形dp.
题意:给定一棵树(n<=300),你可以给每个节点等概率地染成A,B,C三种颜色之一,对于树上的一条边,若其两个端点的颜色不一样,则断开这条边.最后对于一个特定的颜色,X为点数为奇数的联通块个数,Y是点数为偶数的联通块个数,其得分为max(0,X-Y).问最后得分的期望乘上3^n mod 1e9+7的值.
解法:注意到颜色的对称性,我们只需要求出每个颜色的期望再乘上3就可以,而期望就是所有的情况除以3^n(情况种数),所以dp出所有可能的状态的方法数即可.
dp状态:dp[i][j][k],i代表对应的点,j有3个取值,0代表不取当前的点,1代表取当前的点并且当前点所在联通块的个数为奇数个,2代表为偶数个,k代表x-y的值.(注意dp表示的个数并不包括当前根节点的状态,因为当前根节点的状态还要需要其父亲)
状态转移:
dp[u][0][x+y]=dp[u][0][x]*dp[v][0][y]+dp[u][0][x]*dp[v][1][y-1]+dp[u][0][x]*dp[v][2][y+1]
dp[u][1][x+y]=dp[u][1][x]*dp[v][0][y]+dp[u][1][x]*dp[v][2][y]+dp[u][2][x]*dp[v][1][y]
dp[u][2][x+y]=dp[u][2][x]*dp[v][0][y]+dp[u][1][x]*dp[v][1][y]+dp[u][2][x]*dp[v][2][y]
注意dp枚举的过程以及其优化.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MOD = 1000000007;
const int base = 160;
vector<int> g[305];
int dp[305][3][505];
int  t[3][505];
int low[305], high[305];
int n;

void add(int &x, int y)
{
    x += y;
    while (x < MOD) {
        x += MOD;
    }
    while (x >= MOD) {
        x -= MOD;
    }
}

int make_mul(int a, int b, int c, int d, int e, int f)
{
    int v = 0;
    add(v, 1ll * a * b % MOD);
    add(v, 1ll * c * d % MOD);
    add(v, 1ll * e * f % MOD);
    return v;
}

void dfs(int u, int fu)
{
    dp[u][0][base] = 2;
    dp[u][1][base] = 1;
    low[u] = 0, high [u] = 0;
    int size = (int)g[u].size();
    for (int i = 0; i < size; ++ i) {
        int v = g[u][i];
        if (v == fu)    continue;
        dfs(v, u);
        memset(t, 0, sizeof(t));
        for (int x = low[u]; x <= high[u]; ++ x) {
            for (int y = low[v] - 1; y <= high[v] + 1; ++ y) {
                if (x + y > n || x + y < -n)  continue;
                add(t[0][x + y + base], make_mul(dp[u][0][x + base], dp[v][0][y + base], dp[u][0][x + base], dp[v][1][y - 1 + base], dp[u][0][x + base], dp[v][2][y + 1 + base]));
                add(t[1][x + y + base], make_mul(dp[u][1][x + base], dp[v][0][y + base], dp[u][1][x + base], dp[v][2][y + base], dp[u][2][x + base], dp[v][1][y + base]));
                add(t[2][x + y + base], make_mul(dp[u][2][x + base], dp[v][0][y + base], dp[u][1][x + base], dp[v][1][y + base], dp[u][2][x + base], dp[v][2][y + base]));
                if (t[0][x + y + base] != 0) {
                    if (x + y < low[u]) low[u] = x + y;
                    if (x + y > high[u])    high[u] = x + y;
                }
                if (t[1][x + y + base] != 0) {
                    if (x + y < low[u]) low[u] = x + y;
                    if (x + y > high[u])    high[u] = x + y;
                }
                if (t[2][x + y + base] != 0) {
                    if (x + y < low[u]) low[u] = x + y;
                    if (x + y > high[u])    high[u] = x + y;
                }
            }
        }
        for (int j = low[u]; j <= high[u]; ++ j) {
            dp[u][0][j + base] = t[0][j + base];
            dp[u][1][j + base] = t[1][j + base];
            dp[u][2][j + base] = t[2][j + base];
        }
    }
}

int main()
{
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++ i) {
            g[i].clear();
        }
        memset(dp, 0, sizeof(dp));
        int a, b;
        for (int i = 1; i < n; ++ i) {
            scanf("%d%d", &a, &b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(1, 0);
        int ans = 0;
        for (int i = -1; i <= high[1]; ++ i) {
            add(ans, 1ll * max(i, 0) * dp[1][0][i + base] % MOD);
            add(ans, 1ll * max(i + 1, 0) * dp[1][1][i + base] % MOD);
            add(ans, 1ll * max(i - 1, 0) * dp[1][2][i + base] % MOD);
        }
        ans = (int)(3ll * ans % MOD);
        printf("%d\n", ans);
    }
    return 0;
}

参考:http://blog.csdn.net/u011277193/article/details/40735349


  1. 还好我们这边比较人性化,就地铁要检测。公交车不用喝。汽车门口的安检 最近一次我去,人家说 你就打开喝喝装装样子 不用真喝

  2. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  3. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  4. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  5. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  6. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  7. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  8. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  9. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  10. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  11. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  12. 好久没来逛D站了感觉变化好大好大,第一次知道还是2014年,为了看喰种,那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学,他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好!!!!另外站长是我的!!!!

  13. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  14. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  15. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  16. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  17. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  18. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  19. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  20. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……

  21. 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】<意大利希腊13日阳光之旅>圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地,这里有极迷人的阳光与海滩、有优美的 ……