9月10日

1879 ワード

1.ツリーDP入門問題
アドレス:http://acm.hdu.edu.cn/showproblem.php?pid=1520
分析:木の形のDPテーマ、各ノードは権力の値があって、子のノードと父のノードは同時に選ぶことができなくて、最後に選ぶことができる最大の価値はいくらですか?
状態方程式は,dp[u][0]+=max(dp[j][0],dp[j][1]),dp[u][1]+=dp[j][0]; (0はuノードが選択されていないことを示し、1はそのノードが選択されていることを示し、jはuのサブノードである)
コード:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LL long long int
using namespace std;

int val[6010];
int dp[6010][2];
vector vec[6010];
int in[6010];

int dfs(int u)
{
    dp[u][0] = 0, dp[u][1] = val[u];
    for (int i = 0; i < vec[u].size(); ++i)
    {
        int j = vec[u][i];
        dfs(j);
        dp[u][0] += max(dp[j][0], dp[j][1]);
        dp[u][1] += dp[j][0];
    }
    return max(dp[u][0], dp[u][1]);
}

int main()
{
    int n;

    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &val[i]), vec[i].clear(), in[i] = 0;
        int u, v;
        while (scanf("%d%d", &u, &v) && u+v)
        {
            vec[v].push_back(u);
            in[u]++;
        }
        int ans = 0;
        for (int i = 1; i <=n; ++i)
        {
            if (in[i] == 0)
            {
                ans += dfs(i);
                break;
            }
        }
        printf("%d
", ans);
    }

    return 0;
}

ShowModalDialogデータキャッシュの問題

Smartyのコメントと切り捨て機能の紹介