2022-1-4

本文主要是介绍2022-1-4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

poj 2342 Anniversary party

题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，

现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

#include <iostream>
#include <bits/stdc++.h>
const int maxn=6010;
using namespace std;
int dp[maxn][3],fa[maxn],vis[maxn];
vector<int> p[maxn];

void slove(int root){
    vis[root]=1;
    for(int i=0;i<p[root].size();i++){
        if(vis[p[root][i]]==0){
        slove(p[root][i]);
        dp[root][1]=dp[root][1]+dp[p[root][i]][0];
        dp[root][0]=dp[root][0]+max(dp[p[root][i]][1],dp[p[root][i]][0]);
        }
    }
  return ;
}

int main()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++){
    cin>>dp[i][1];
   }
    int b,c;
   while(cin>>b>>c){
    if(b==0&&c==0) break;
    fa[b]=c;
    p[c].push_back(b);
   }
   int m=fa[1],root;
   while(m!=0)
    root=m,m=fa[m];
   slove(root);
   cout<<max(dp[root][1],dp[root][0])<<endl;
    return 0;
}

Rebuilding Roads [ 树形dp]

题意：
有n个点组成一棵树，问至少要删除多少条边才能获得一棵有p个结点的子树？

思路：
dp[root][j]：以root为根节点的子树，得到 j 个节点的子树需要最少减掉的边数，注意子树中必须保留root节点。否则无法dp
那么很明显的边界条件dp[root][1] = num（儿子的个数），因为要只剩一个节点的子树，那么所有的孩子都减掉，这样就为儿子的个数。
那么状态转移方程呢
dp[root][i] = min（dp[root][i-k]+dp[son][k] - 1，dp[root][i]）；
其实就是要得到一个i个节点的子树，枚举所有的孩子为k个节点的，当前root保留 i-k 个节点，然后把root和child之间之前被剪断的连接起来，所以这里要减1


树形dp 重要就是先解决子树 ，即c从下往上；
 本题一个节点下有多个子节点（多个子树）； 先利用一个子节点更新答案，再利用另个子节点更新答案（此时，该节点已经使用上个子节点更新答案，）
 所以满足逐个使用子节点更新答案； 当用完最后一个子节点；该节点答案已经完全；
 所以slove函数中第二个循环j 从p开始（从大到小去找满足该子节点的结果）【若从小到大，就会出现在一层循环里（一个子节点），j=p-1 被j = p使用（小的已经算出，大的会用小的】
这样的话，在遍历其他子节点时，上个节点已经算出，会再次利用算出的值去计算

#include <iostream>
#include <bits/stdc++.h>
const int INF=0x3f3f3f3f;
using namespace std;

vector<int> v[200];
int dp[200][200],vis[200],fa[200],ru[200];;
int n,p;
void slove(int root){
    vis[root]=1;
    for(int i=0;i<v[root].size();i++){
        if(!vis[v[root][i]]){
           slove(v[root][i]);
            for(int j=p;j>=1;j--){ // j从大到小
            for(int k=1;k<j;k++){
                dp[root][j]=min(dp[root][j],dp[root][j-k]+dp[v[root][i]][k]-1);
            }
            //cout<<root<<" "<<j<<" "<<dp[root][j]<<" "<<v[root][i]<<endl;
            }
        }
    }

}

int main()
{
    cin>>n>>p;
    int nn=n;
    int a,b;
    n--;
    memset(dp,INF,sizeof(dp));
    memset(ru,0,sizeof(ru));
    while(n--){
      cin>>a>>b;
      ru[a]++;
      fa[b]=a;
      v[a].push_back(b);
      dp[a][0]=0;
      dp[b][0]=0;
    }
    for(int i=1;i<=nn;i++) dp[i][1]=ru[i];
    int m,root;
    m=fa[1];root=1;
    while(m!=0){
        root=m;
        m=fa[m];
    }
     //cout<<root<<endl;
    slove(root);
    int ans=dp[root][p];
    cout<<dp[1][p];
    for(int i=2;i<=nn;i++){
        ans=min(ans,dp[i][p]+1);
    }
        cout<<ans<<endl;
    return 0;
}

树形dp - H.Crystalfly

#include <bits/stdc++.h>
using namespace std;

const int maxn=100100;
vector<int> g[maxn];
int sum[maxn],f[maxn],a[maxn],t[maxn];
int n;
void init(){
  for(int i=1;i<=n;i++){
    g[i].clear();
    sum[i]=0;
    f[i]=0;
  }
}

void slove(int u,int par){
    int t1=0,t2=0;
    if (g[u].size() == 1 && par != -1) {
		return;
	}
    for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==par) continue;
        slove(x,u);
        sum[u]+=f[x];
    }
     for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==par) continue;
        t1=max(t1,sum[u]+a[x]);
     }
     int maxx=0,w=0;
     for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x!=par&&t[x]==3&&a[x]>maxx) {
            maxx=a[x];w=x;
     }
     }
     if(w!=0)
     for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==par) continue;
        if(w==x) continue;
        t2=max(t2,a[w]+sum[x]-f[x]+a[x]+sum[u]);
     }
     for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==par) continue;
        if(x==w) continue;
        if(t[x]==3)
            t2=max(t2,a[x]+sum[w]-f[w]+a[w]+sum[u]);
     }
     f[u]=max(t1,t2);
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        init();
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>t[i];
        for(int i=1;i<=n-1;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        slove(1,-1);
        cout<<f[1]+a[1]<<endl;
    }
    return 0;
}

这篇关于2022-1-4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！