藍橋杯 - 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（遞歸）