本文主要是介绍UVa1218 Perfect Service，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
稍复杂的树型dp。。状态的类型不仅跟当前节点有关，还与当前节点的父节点有关。一共有三种状态，当前节点是服务器，当前节点不是且父节点是，当前节点不是且父节点不是。dp的时候直接把不可能状态的费用置为无穷大，这样求出的解就不会是不可能状态。。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 10000
#define ll long long
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010using namespace std; vector<int> E[10010];
int dp[10010][3];/** 0都不是 * 1自己是 * 2父亲是 */
int fun(int u,int f,int type){if(dp[u][type]!=-1)return dp[u][type];int re=0;if(type==1){for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re+=min(fun(E[u][i],u,1),fun(E[u][i],u,2));}re++;}if(type==0){int tmp=0;re=INF;for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;tmp+=fun(E[u][i],u,0);}//换掉一个 for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re=min(re,tmp-fun(E[u][i],u,0)+fun(E[u][i],u,1));}if(E[u].size()==1&&f!=-1)re=INF;}if(type==2){for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re+=fun(E[u][i],u,0);}}dp[u][type]=re;return re;
}int main(){int N;while(cin>>N){memset(dp,-1,sizeof(dp));for(int i=1;i<=N;i++)E[i].clear();int u,v;for(int i=1;i<N;i++){cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}cout<<min(fun(1,-1,0),fun(1,-1,1))<<endl;int end;cin>>end;if(end==-1)break;}return 0;
}
这篇关于UVa1218 Perfect Service的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
