蒟蒻的树形dp记录

时间：2021-07-09 05:45:47

POJ2342：

题意：某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

题解：

当i来的时候，dp[i][1] += dp[j][0];//j为i的下属

当i不来的时候，dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

//#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

#define inf 10000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************************************

int dp[][];

int vis[];

int parent[];

int n,a,b;

void sp(int x)

{

    vis[x]=;

    for(int i=;i<=n;i++)

    {

        if(parent[i]==x&&!vis[i])

        {

            sp(i);

            dp[x][]+=max(dp[i][],dp[i][]);

            dp[x][]+=dp[i][];

        }

    }

}

int main()

{

    while(cin>>n)

    {  memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++)

            scanf("%d",&dp[i][]);

            memset(vis,,sizeof(vis));

            int root=;

            memset(parent,,sizeof(parent));

        while(scanf("%d%d",&a,&b)&&a&&b)

        {

            parent[a]=b;

            root=b;

        }

        sp(root);

        printf("%d\n",max(dp[root][],dp[root][]));

    }

    return ;

}

代码狗

vijos1642

题解：我们先依次求出每棵树的先根遍历序，并保存在同一个序列list[]中。 为了利用上面的结论，我们还要求出以节点i为根的子树的节点总数count[i]。

定义： v[i]表示第i个物品的权值 dp[i][j]表示从第i个物品到第n个物品，最多花费j，能得到的最大权值和。

状态转移： 对于一个节点，我们考虑是否购买它： 购买：那么我们继续考虑它后面的节点 不购买：那么我们跳过它的子孙节点

方程如下： F[i][j]=Max{F[i+1][j-cost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}

///

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

typedef long long ll;

using namespace std;

#define inf 10000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************************************

///先根遍历序

int list[];

int s[],a[][];

int v[],counts[];

int dp[][];

int q;

int n,m;

int dfs(int k)

{

    list[++q]=k;

    if(s[k]==){return ++counts[k];}

    for(int i=;i<=s[k];i++)

    {

        counts[k]+=dfs(a[k][i]);

    }

    return ++counts[k];

}

int main()

{

 int  t;

     memset(dp,-,sizeof(dp));

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     {

         scanf("%d%d",&v[i],&t);

     while(t--)

         {

             scanf("%d",&a[i][++s[i]]);

         }

     }

     dfs();

     for(int i=;i<=n;i++){dp[i][]=;dp[i][]=v[list[i]];}

       for(int i=n-;i>=;i--)

       {

           for(int j=;j<=m;j++)

           {

               dp[i][j]=max(dp[i+][j-]+v[list[i]],dp[i+counts[list[i]]][j]);

           }

       }

       int ans=-inf;

       for(int i=;i<=m;i++)

        ans=max(dp[][i],ans);

        printf("%d\n",max(ans,));

    return ;

}

代码狗

 POJ 1947

题解：dp[root][i]表示以root为根得到节点数为i 所需要删除的少边数

转移：

dp[root][i]=dp[root][i]+1;  不加某son，边+1；

dp[root][i]=min(dp[root][i-j]+dp[son][j]);加某son，j代表son为根的树节点数

最后注意：非根节点边数+1；因为要删除与父亲节点的边

///

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

typedef long long ll;

using namespace std;

#define inf 10000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************************************

int dp[][];

vector<int  >son[];

int dfs(int root,int pre)

{

    dp[root][]=;

    int sum=;

    for(int i=;i<son[root].size();i++)

    {

        int s=son[root][i];

        if(s==pre)continue;

        sum+=dfs(s,root);

        for(int  k=sum;k>=;k--)

        {

            dp[root][k]=dp[root][k]+;

            for(int h=;h<k;h++)

            {

                dp[root][k]=min(dp[root][k],dp[root][k-h]+dp[s][h]);

            }

        }

    }

    return sum;

}

int main()

{

    int n,m,a,b;

    memset(dp,,sizeof(dp));

    scanf("%d%d",&n,&m);

   // for(int i=1;i<=n;i++)dp[i][0]=1;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&a,&b);

        son[a].push_back(b);

        son[b].push_back(a);

    }

    dfs(,-);

    int ans=dp[][m];

    for(int i=;i<=n;i++){

        if(dp[i][m]+<ans)ans=dp[i][m]+;

    }

    printf("%d\n",ans);

    return ;

}

代码

 HDU 1011 Starship Troopers

转移：dp[i][k] = max(dp[i][k], dp[i][k-l] + dp[i][l]);

//зїеп:1085422276

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

#include <stack>

typedef long long ll;

#define inf 100000000

using namespace std;

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************

int v[];

int cost[];

int dp[][];

vector<int >tr[];

int n,m;

void dfs(int k,int pre)

{

    for(int i=cost[k];i<=m;i++)

        dp[k][i]=v[k];

    for(int i=;i<tr[k].size();i++){

        if(pre==tr[k][i])continue;

        dfs(tr[k][i],k);

        int son=tr[k][i];

        for(int j=m;j>=cost[k];j--)

        {

            for(int l=;l+cost[k]<=j;l++)

            {

                dp[k][j]=max(dp[k][j],dp[son][l]+dp[k][j-l]);

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==-&&m==-)break;

       // init();

       memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++)

        {

            scanf("%d%d",&cost[i],&v[i]);

            cost[i]=cost[i]/+(cost[i]%!=);

           // if(cost[i]%20!=0)cost[i]+=1;

            tr[i].clear();

        }

        int a,b;

        for(int i=;i<n;i++)

        {

            scanf("%d%d",&a,&b);

            tr[a].push_back(b);

            tr[b].push_back(a);

        }

        if(m==){printf("0\n");continue;}

        dfs(,-);

        printf("%d\n",dp[][m]);

    }

    return ;

}

代码

CodeForces 161D Distance in Tree

题目链接：http://codeforces.com/contest/161/problem/D

简单树形dp：维护各个节点1到k的情况就可以了；

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//**************************************************************************************

ll ans,dp[][];///以i为节点构成路径长度为j的种类树；

vector<int >G[];

int fa[];

int vis[];

int n,m;

void  dfs(int k)

{

    dp[k][]=;

  for(int i=;i<G[k].size();i++){

    int son=G[k][i];

    if(vis[son])continue;

    vis[son]=;

    dfs(son);

    for(int j=;j<m;j++){

        ans+=dp[k][m-j-]*dp[son][j];

    }

    for(int i=;i<=m;i++)

    {

        dp[k][i]+=dp[son][i-];

    }

  }

}

int main()

{

    scanf("%d%d",&n,&m);

    int a,b;

    for(int i=;i<n;i++){

        scanf("%d%d",&a,&b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    memset(vis,,sizeof(vis));

    memset(dp,,sizeof(dp));

    vis[]=;

    dfs();

   cout<<ans<<endl;

    return ;

}

代码

 【tyvj1520】树的直径

题目链接：http://www.tyvj.cn/p/1520

dp1[]，dp2[]分别代表从当前根节点出发所能到达的最长链与次长链，感谢HZWER指点；。。。。。

///

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

typedef long long ll;

using namespace std;

#define inf 10000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************************************

struct ss

{

    int to,next,v;

}e[*];

int head[],t,dp1[],dp2[],ans;

void add(int u,int v,int w)

{

    e[t].to=v;

    e[t].next=head[u];

    e[t].v=w;

    head[u]=t++;

}

void dp(int x,int pre)

{

    for(int i=head[x];i;i=e[i].next)

    {

        if(e[i].to==pre)continue;

        dp(e[i].to,x);

        if(dp1[e[i].to]+e[i].v>dp1[x])

        {

            dp2[x]=dp1[x];

            dp1[x]=dp1[e[i].to]+e[i].v;

        }

        else dp2[x]=max(dp1[e[i].to]+e[i].v,dp2[x]);

    }

    ans=max(dp1[x]+dp2[x],ans);

}

int main()

{int n;

memset(head,,sizeof(head));

t=;

ans=;

int u,v,w;

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dp(,);

    cout<<ans<<endl;

    return ;

}

代码

相关文章