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; }