洛谷 P1352 没有上司的舞会【树形DP/邻接链表+链式前向星】-白红宇

洛谷 P1352 没有上司的舞会【树形DP/邻接链表+链式前向星】

阅读量：7211 次

发布时间：2019-06-29

本文共 4203 字，大约阅读时间需要 14 分钟。

题目描述

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入输出格式

输入格式：

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式：

输出最大的快乐指数。

【分析】：

那么考虑树形DP的状态设计，一般与子树有关，即求出子树的答案然后合并上去

考虑在合并的时候，会影响答案合并的状态，就是子树的根节点选或者不选了，选了的话当前节点就不能选，两者的答案不一样当然要分开统计

于是得出状态设计： f(i,0/1)

表示第i个子树内，i这个点选或者不选的最大值

f(i,0) = sigma max(f(v,0),f(v,1)) + ai，这是由于只要根不选，子树选不选都可以的缘故

f(i,1) = sigma f(v,0) ，这是由于根选了，所有子树的根都不能选的缘故

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxn = 1e5 + 20;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0}};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longusing namespace std;int h[maxn];int v[maxn];int n;vector
                       
                         son[maxn];int f[maxn][2];void dfs(int x){ f[x][0]=0; f[x][1]=h[x]; for(int i=0;i
                        
                         >n; rep(i,1,n) cin>>h[i]; rep(i,1,n-1) { int x,y; cin>>x>>y; son[y].push_back(x); v[x]=1; } int root; rep(i,1,n) { if(!v[i]) { root=i; break; } } dfs(root); cout<
                         
                          <

HDU 1520 【链式前向星版本】

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxn = 100010 + 20;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0}};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longusing namespace std;int h[maxn];int v[maxn];int n;int f[maxn][2];int head[maxn];struct node{ int to,nxt;}e[maxn*2];int tot=0;void add(int u,int v){ tot++; e[tot].to=v; e[tot].nxt=head[u]; head[u]= tot;}void init(){ tot=0; ms(head,-1); ms(f,0); ms(v,0);}void dfs(int u,int fa){ //f[u][0]=0; f[u][1]=h[u]; for(int i=head[u]; i!=-1; i=e[i].nxt) { int v=e[i].to; if(v==fa) continue; dfs(v,u); f[u][0] += max(f[v][0],f[v][1]); f[u][1] += f[v][0]; }}int main(){ while(cin>>n) { init(); rep(i,1,n) cin>>h[i]; rep(i,1,n-1) { int x,y; cin>>x>>y; add(x,y), add(y,x); v[x]++; } scanf("\n0 0"); int root; rep(i,1,n) if(!v[i]) { root=i; break; } dfs(root,root); cout<
                       
                        <

转载于:https://www.cnblogs.com/Roni-i/p/9409764.html

你可能感兴趣的文章