蓝桥杯 - G将军(树）

2019-11-08 03:18:38

字体：大中小

来源：转载

供稿：网友

G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进入敢死队。输入格式输入的第一行包含一个整数n，表示包括G将军在内的军队的人数。军队的士兵从1至n编号，G将军编号为1。接下来n-1个数，分别表示编号为2, 3, ..., n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。输出格式输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出这个数除10007的余数即可。样例输入131 1样例输出14样例说明这四种方式分别是：1. 选1；2. 选2；3. 选3；4. 选2, 3。样例输入271 1 2 2 3 3样例输出240数据规模与约定对于20%的数据，n ≤ 20；对于40%的数据，n ≤ 100；对于100%的数据，1 ≤ n ≤ 100000。资源约定：峰值内存消耗 < 256MCPU消耗 < 2000ms思路参考学长的博客：点击打开链接自己肯定写的没他好，就直接放他的思路了： 首先，可以去百度一下公司party那题，树状dp经典。 然后回过头来看这题，在树状上做动态规划和这题的难点。dp[i][0]代表第i个节点的人不去的方案数，dp[i][1]代表第i个节点去的方案数，然后难点来了， i节点的去于不去的方案数和什么有关呢，仔细分析得到，如果i节点去了，那么他的下属都不能去，那么dp[i][1]=dp[j][0]*dp[k][0]*dp[x][0]`````(j,k,x都是i节点的下属，为什么用的是乘法呢，这是应用到了乘法原理，下边还会用到) i节点去的情况分析完了，那么不去的情况是否也是那么简单呢，比赛之后我自己想了想dp[i][0]=dp[j][0]*dp[k][1]+dp[j][1]*dp[k][1]+dp[j][0]*dp[k][1] (现在是假设i节点只有j和k两个子节点也就是下属，看出来什么规律没有，这就是乘法原理，当时我直接就把所有人都不去的情况没算进去，可是发现若是在多一个节点，这个多项式就要从现在的3项相加变成7项相加，再多两个呢，多更多呢，最后就一直拖到昨天都没想出来，然后今天学长启发了我，说可以把那个所有人都不去的情况先算在内，最后输出答案的时候减1就行了。)这样，通过乘法原理，就简化出了上边代码中的 dp[i][0]=(dp[j][0]+dp[j][1])*·········;，其中j为i的子节点。 至此，递推式出来了 dp[i][1]=dp[j][0]*dp[k][0]*dp[x][0]````` j,k,x都是i节点的下属 dp[i][0]=(dp[j][0]+dp[j][1])*·········;，其中j为i的子节点。 但是不要忽略这题为什么叫树状dp，树状，还要基于树，在算法中，图常常用邻接表来储存，这又是此题的一难点，用一个vector<int> m[N] 这样的数组来存储这棵数，m[i]的类型就是一个vector<int> 通俗了说m就是一个 vector<int> 型的数组，常常用这种结构来存储稀疏矩阵。m[i]这个的vector里边存的就是i节点的子节点例如如果节点1子节点有 7和8，那么 m[1].size()=2,m[1][0]=7,m[1][1]=8(因为vector的特点是可以通过下标的方式取值，具有极大的便利)，最后，就是如上的代码，得到的递推式最终形式是 dp[i][1]*=dp[m[i][j]][0];dp[i][0]*=(dp[m[i][j]][0]+dp[m[i][j]][1]); （其中m[i][j]就是i节点的子节点，j=0,1,2,3.....) 然后把每个节点的初始值赋值成1，应为叶子节点时，没有下属，他去和不去只和他自己有关，去是一种方案，不去也是一种方案，而树枝节点的乘法运算也需要赋个初始值1，这样就干脆直接写进第一层循环，大功告成o(≧v≦)o~~，，on！不对，忘了说最后的答案是什么了，最后的方案总数应该是根节点去dp[root][1]和不去dp[root][0]之和，再减去所有人都不去的1种情况，好了，然后别忘了模上10007，输出答案。（最好-1之后再加上个mod，可能dp[1][0]+dp[1][1]正好是0,这样结果就变成了-1）有两种写法，可以是递归形式；题目还说了上司的序号一定比自身小，所以又可以写成for循环形式倒着递推；方法一（递归）：

#include<iostream>#include<vector>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1e5+5;const int mod = 1e4+7;vector<int> m[maxn];int dp[maxn][2], n;void dfs(int r){    dp[r][0] = dp[r][1] = 1;    for(int i = 0; i < m[r].size(); i++)    {        int child = m[r][i];        dfs(child);        dp[r][0] = dp[r][0]*(dp[child][0]+dp[child][1])%mod;        dp[r][1] = dp[r][1]*dp[child][0]%mod;    }}int main(void){    while(cin >> n)    {        memset(dp, 0, sizeof(dp));        for(int i = 0; i < maxn; i++)            m[i].clear();        for(int i = 2; i <= n; i++)        {            int t;            scanf("%d", &t);            m[t].push_back(i);        }        dfs(1);        PRintf("%d/n", (dp[1][0]+dp[1][1]-1+mod)%mod);    }    return 0;}方法二（递推）：#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const int maxn = 1e5+5;const int mod = 1e4+7;int dp[maxn][2];vector<int> m[maxn];int main(void){    int n;    while(cin >> n)    {        memset(dp, 0, sizeof(dp));        for(int i = 0; i < maxn; i++)            m[i].clear();        for(int i = 2; i <= n; i++)        {            int t;            scanf("%d", &t);            m[t].push_back(i);        }        for(int i = n; i > 0; i--)        {            dp[i][0] = dp[i][1] = 1;            for(int j = 0; j < m[i].size(); j++)            {                dp[i][1] = (dp[i][1]*dp[m[i][j]][0])%mod;                dp[i][0] = dp[i][0]*(dp[m[i][j]][0]+dp[m[i][j]][1])%mod;            }        }        printf("%d/n", (dp[1][0]+dp[1][1]-1+mod)%mod);    }    return 0;}

上一篇：linux中vim的配置

下一篇：求24（递归）