Anniversaryparty樹形dp-創(chuàng)新互聯(lián)

簡(jiǎn)單的樹形dp

dp[i] 表示以i為根的包括i 的大歡樂度

專業(yè)從事成都網(wǎng)站建設(shè)、做網(wǎng)站,高端網(wǎng)站制作設(shè)計(jì),微信小程序,網(wǎng)站推廣的成都做網(wǎng)站的公司。優(yōu)秀技術(shù)團(tuán)隊(duì)竭力真誠(chéng)服務(wù)，采用H5頁(yè)面制作+CSS3前端渲染技術(shù)，響應(yīng)式網(wǎng)站設(shè)計(jì)，讓網(wǎng)站在手機(jī)、平板、PC、微信下都能呈現(xiàn)。建站過程建立專項(xiàng)小組，與您實(shí)時(shí)在線互動(dòng)，隨時(shí)提供解決方案，暢聊想法和感受。

f[i] 表示以i為根不包括i 的大歡樂度

葉節(jié)點(diǎn)則為 f[i] = 0, dp[i] = w[i]  只要初始化 dp f 都全為0 就可以了 dfs會(huì)自動(dòng)復(fù)制

說實(shí)話我覺得這題很不嚴(yán)謹(jǐn) 他說歡樂度可以為負(fù)值  按理來說如果小于0 就應(yīng)該將歡樂度設(shè)為0 表示那個(gè)人不參加

最后是 無論設(shè)不設(shè)為0 都AC 證明根本沒有歡樂度為負(fù)值的

要注意的是

1. 不是只有一個(gè)case  我一開始以為只有一個(gè)case  一直錯(cuò) 要處理到?jīng)]有輸入為止。。。 題目又沒說明

2. 有可能有多棵樹 所以要多次dfs()

View Code

Anniversary party

Time Limit :2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) :5   Accepted Submission(s) : 2
Font: Times New Roman| Verdana | Georgia
Font Size: ← →
Problem Description
Thereis going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.Input
Employees are numberedfrom 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form: 
L K 
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line 
0 0
Output
Output should contain the maximal sum of guests' ratings.Sample Input
711111111 32 36 47 44 53 50 0
Sample Output
5

View Code

#include <stdio.h>
#include<algorithm>
#include<string.h>

const int MAXN = 6005;
struct node
{
int index ;
    node*next ;
}adj[MAXN];
bool vis[MAXN], isRoot[MAXN];
int n, m, f[MAXN], dp[MAXN], w[MAXN]; 
void addEdge(int x, int y)
{
    node*p = new node;
    p->index = y;
    p->next = adj[x].next;
    adj[x].next= p;
    isRoot[y]= 0;
}
int max(int a, int b)
{return a>=b ?a :b  ;  }
void dfs(int root)
{
    vis[root]= 1;
    node*p = adj[root].next;
while( p != NULL )
    {
int u = p->index;
if(!vis[u])
        {
            dfs(u);
//    dp[root] += f[u]<0 ?0 :f[u];
//    int tmp = max(dp[u], f[u]);
//    f[root] += tmp < 0 ? 0 : tmp ;            dp[root] += f[u];
            f[root]+= max(dp[u], f[u]);
        }
        p= p->next;
    }
    dp[root]+= w[root];
}
int main()
{
int i, a, b, root, ans = 0;
while(scanf("%d", &n)!=EOF)
    {
        ans= 0;
for(i=1; i<=n; i++)
        {
            scanf("%d", &w[i]);
            isRoot[i]= 1; dp[i] = f[i] = 0;
            adj[i].next= NULL, vis[i] = 0;
        }
while(scanf("%d %d", &a, &b), a|b)
            addEdge(b, a);
for(i=1; i<=n; i++)
if(isRoot[i])
            {
                dfs(i);
                ans+= max(dp[i], f[i]);
            }
            printf("%d
", ans);
    }
return 0;
}

當(dāng)前題目：Anniversaryparty樹形dp-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article20/djjgco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、標(biāo)簽優(yōu)化、網(wǎng)站制作、企業(yè)網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)