POJ 1694 An Old Stone Game ★(排序+树+递归)

题解转自：http://blog.sina.com.cn/s/blog_7c060f190100r4cr.html 自己不想再写了……囧…… 题意：以树作为载体，模拟一个游戏。大致规则就是在叶节点上放若干石子，每当一个节点的子节点都有石子时，子节点的石子可以拿掉，在这个节点上放置一个石子，其他石子继续用，直到根节点有石子为止，求出需要的最少的石子。对任意一个节点，只有当他的所有子节点全部被占时，这个点才可能被占。而要占据它的全部子节点，需要多少石子呢？显然，递归之！假设我们已经知道了这所有子节点所需石子数，将其排序。这样，就出现了两种情况： 1、各节点所需石子数均不相同，假设需要石子数关系为an>an-1>…>a1，因为占据这个节点需要一个石子。所以，加入我们取an个石子，先占节点n，因为(an)-1>=an-1，所以占an-1节点的石子数也足够了，以此类推，最少需要an个石子。 2、存在石子数相同的节点，假设石子数关系为an=an-1=…=ai-1>ai，因为每个节点都消耗一个石子，所以ai最多需要(ai)+i-1个石子。从上面两种情况总结来看，在整个过程中，只需比较(ai)+i-1的大小并将其排序，最大值就是占据这个节点所需的最小石子数。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long LL;

vector  child[205];
bool vis[205];
bool cmp(int a, int b){
    return a > b;
}
int solve(int p){
    vis[p] = 1;
    if (child[p].size() == 0)
        return 1;
    else{
        int step[205];
        memset(step, 0, sizeof(step));
        for (int i = 0; i < (int)child[p].size(); i ++){
            step[i] = solve(child[p][i]);
        }
        sort(step, step + (int)child[p].size(), cmp);
        int ret = step[0];
        for (int i = 1; i < (int)child[p].size(); i ++){
            ret = max(ret, step[i] + i);
        }
        return ret;
    }
}
int main(){
    int M, N;
    scanf("%d", &M);
    while(M --){
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < 205; i ++)
            child[i].clear();

        scanf("%d", &N);
        for (int i = 0; i < N; i ++){
            int root, sonnum, son;
            scanf("%d %d", &root, &sonnum);
            for (int j = 0; j < sonnum; j ++){
                scanf("%d", &son);
                child[root].push_back(son);
            }
        }
        printf("%d\n", solve(1));
    }
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG