Luogu-P2015 Binary Apple Tree

subject

Title Link

 

Test score: 100

 

 

Main Algorithms: Tree DP, One Backpack

 

 

Topics:

* Zero-one DP on the tree

 

 

Examination strategy:

  1. Memorized Search
  2. If it is an empty node
  3. Return the number of apples directly if it is a leaf node
  4. If none of the above is satisfied, DP state transition
  5. Set up DP transfer to left and right son nodes
  6. for(int i=1;i<cnt-1;i++) f[u][cnt]=max(f[u][cnt],Dp(edge[p[u].lc].to,i)+Dp(edge[p[u].rc].to,cnt-i-1)+edge[p[u].lc].dis+edge[p[u].rc].dis);
  7. Result 31 points

Error Cause Analysis:

1. To put it plainly, memorized search is not very good at it

2. Secondly, the state design is not particularly good. When storing left and right sons, you should need to store the edges.

Code

 

#include<stdio.h>
#include<stdlib.h>
#define int long long 
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)

using namespace std;
const int N=200;
int n,num_edge,q,head[N+1],f[N+1][N+1];
struct Edge{
    int next,to,dis;
}edge[2*N+2];
struct Mess{
    int lc,rc;
}p[N+1];
inline void Add_edge(int from,int to,int dis)
{
    edge[++num_edge]=(Edge){head[from],to,dis},head[from]=num_edge;
}
inline int max(int fa,int fb){return fa>fb?fa:fb;}

void Dfs(int u,int fa)
{
    for(int i=head[u];i;i=edge[i].next)
    {
        if(edge[i].to!=fa)
        {
            if(!p[u].lc) p[u].lc=i;
            else p[u].rc=i;
            Dfs(edge[i].to,u);
        }
    }
}
int Dp(int u,int cnt)
{
    if(!cnt) return 0;
    if(!p[u].lc&&!p[u].rc) return edge[p[u].lc].dis+edge[p[u].rc].dis;
    if(f[u][cnt]) return f[u][cnt];
    f[u][cnt]=max(f[u][cnt],Dp(edge[p[u].lc].to,0)+Dp(edge[p[u].rc].to,cnt-1)+edge[p[u].rc].dis);
    f[u][cnt]=max(f[u][cnt],Dp(edge[p[u].lc].to,cnt-1)+Dp(edge[p[u].rc].to,0)+edge[p[u].lc].dis);
    for(int i=1;i<cnt-1;i++)    f[u][cnt]=max(f[u][cnt],Dp(edge[p[u].lc].to,i)+Dp(edge[p[u].rc].to,cnt-i-1)+edge[p[u].lc].dis+edge[p[u].rc].dis);
    return f[u][cnt];
}
void main()
{
    int from,to,dis;
    scanf("%d%d",&n,&q),++q;
    FORa(i,2,n)
    {
        scanf("%d%d%d",&from,&to,&dis);
        Add_edge(from,to,dis),Add_edge(to,from,dis);
    }
    Dfs(1,0);
    printf("%d",Dp(1,q));
    return 0;
}
/*5 2
1 3 1
1 4 10
2 3 20
3 5 20*/

 

Optimizing strategy:

- Memory Search, Tree Backpack DP

This question has an implicit condition that when an edge is preserved, all edges along the path from the root node to the edge must also be preserved

Set f[u][i] to denote the number of apples that remain at most I I edges on a subtree of u u

Then the state transfer equation is obvious

FORs(j,min(sz[u],m),0)//01 backpack, can only be selected once for each option
      FORa(k,0,min(sz[v],j-1))
      f[u][j]=max(f[u][j],f[v][k]+f[u][j-k-1]+edge[i].dis);

U denotes the current node, v is a child node of u, sz[u] denotes the number of edges on the subtree of u u, m is the maximum number of reserved edges required in the title

Why then?

First, why is f[u][i-j-1] not f[u][i-j]?

As mentioned earlier, reserving an edge must preserve all edges along the path from the root node to this edge, so if you want to reserve an edge from a subtree of the child node v of u, you must also reserve an edge between u and v

Why should the range k be less than or equal to i_1 instead of I i?

Same as above, because u,v are connected

Yes, don't forget i,j enumerates in reverse order because this is 01 Backpack

Code

#include<stdio.h>
#include<stdlib.h>
#define LL long long 
#define FORa(i,s,e) for(LL i=s;i<=e;i++)
#define FORs(i,s,e) for(LL i=s;i>=e;i--)

using namespace std;
const LL N=1000;
LL n,m,num_edge,sz[N+1],head[N+1],f[N+1][N+1];
/*f[u][j]Represents the maximum number of apples that retain j branches in a subtree with a root of u 
sz[u]Represents the size of a subtree whose root is u 
*/
struct Edge{
    LL next,to,dis;
}edge[2*N+2];
struct Mess{
    LL lc,rc;
}p[N+1];
inline void Add_edge(LL from,LL to,LL dis)
{
    edge[++num_edge]=(Edge){head[from],to,dis},head[from]=num_edge;
}
inline LL max(LL fa,LL fb){return fa>fb?fa:fb;}
inline LL min(LL fa,LL fb){return fa<fb?fa:fb;}

void Dfs(LL u,LL fa)
{
    sz[u]=1;
    for(LL i=head[u];i;i=edge[i].next)
    {
        LL v=edge[i].to;
        if(v!=fa)
        {
            Dfs(v,u);
            sz[u]+=sz[v];
            FORs(j,min(sz[u],m),0)//One Backpack, only once for each option 
                FORa(k,0,min(sz[v],j-1))
                    f[u][j]=max(f[u][j],f[v][k]+f[u][j-k-1]+edge[i].dis);
            /*For state transition, the maximum number of apples with u as root and j branches retained
            Equals the number of apples with the son node of u as the root, the maximum number of apples with j-k-1 branches reserved plus the root with v, and the maximum number of apples with K (k<=min (sz[v], j-1)) branches reserved*/
        }
    }
}
int main()
{
    LL from,to,dis;
    scanf("%lld%lld",&n,&m);
    FORa(i,2,n)
    {
        scanf("%lld%lld%lld",&from,&to,&dis);
        Add_edge(from,to,dis),Add_edge(to,from,dis);
    }
    Dfs(1,0);
    printf("%lld",f[1][m]);
    return 0;
}
/*5 2
1 3 1
1 4 10
2 3 20
3 5 20*/

 

Summary:

1.DP status design must be remembered by itself

2.DP Initialization and Boundary Processing

 

 

Tags: PHP less

Posted on Tue, 06 Aug 2019 17:52:12 -0700 by direction