PRoblem: 给一棵树，问最少砍多少刀就可以划分出来一个p个节点的子树。 Solution: 对于一个根节点i，我们定义这个i一定在最终划分出来的子树当中，dp[i][k]表示以i为根节点的子树划分出k个节点所需要的最少次数。那么dp[i][j+k] = min(dp[i][j+k], dp[i][j]+dp[son[i]][k]-1)。这个状态转换理解为：对于i为根节点的这颗子树，需要划分出来j+k个节点，那么我们可以从这个儿子中划分出来k个，从其它部分划分出来j个，-1是因为要把儿子那部分合并进来，就需要减一刀。最终动规完毕后，需要再遍历一遍所有节点，找到以哪个节点为根节点的子树才是最优解，而最后需要加上1，表示从原来的子树中分离出去。由于我们初始化ans的值为dp[root][p],所以我们也无需担心根节点这个答案+1后超出原来的值。有一些细节需要注意，具体看代码。 notes: 1. 没有处理0，而是放在最后处理，因为划分出来1个节点也是0刀，避免dp冲突，最后再遍历一遍即可。 2. dp[x][1]就代表其它兄弟节点不贡献值，所以也不用处理0这种情况。
#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<ctime>#include<vector>#include<fstream>#include<list>#include<numeric>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;int dp[155][155];int fa[155];vector<int> Tree[155];int n, p;void solve(int x) { for(int i = 0; i < Tree[x].size(); i++) solve(Tree[x][i]); dp[x][1] = Tree[x].size(); for(int i = 0; i < Tree[x].size(); i++) { for(int j = p-1; j > 0; j--) { if(dp[x][j] != INF) { for(int k = 1; k <= p-j; k++) { if(dp[Tree[x][i]][k] != INF) dp[x][j+k] = min(dp[x][j+k], dp[Tree[x][i]][k]+dp[x][j]-1); } } } }}int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int a, b, ans, root = 1; ms(fa); for(int i = 0; i <= 150; i++) for(int j = 0; j <= 150; j++) dp[i][j] = INF; cin >> n >> p; for(int i = 1; i < n; i++) { cin >> a >> b; fa[b] = a; Tree[a].push_back(b); } while(fa[root] != 0) root = fa[root]; solve(root); ans = dp[root][p]; for(int i = 1; i <= n; i++) if(dp[i][p] < ans) ans = dp[i][p]+1; cout << ans << endl; return 0;}新闻热点
疑难解答
