欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解樹(shù)形DP

 更新時(shí)間:2021年05月31日 14:24:33   作者:zhxmdefj  
樹(shù)形DP是什么?跟其他DP有什么區(qū)別?相信很多初學(xué)者在剛剛接觸一種新思想的時(shí)候都會(huì)有這種問(wèn)題。沒(méi)錯(cuò),樹(shù)形DP準(zhǔn)確的說(shuō)是一種DP的思想,將DP建立在樹(shù)狀結(jié)構(gòu)的基礎(chǔ)上。所以我們結(jié)合具體題目進(jìn)行講解,希望大家可以在題目中領(lǐng)悟這種思想。

前言

給定一顆有N個(gè)節(jié)點(diǎn)的樹(shù)(一般是無(wú)根樹(shù),就有N-1條無(wú)向邊),可以任選一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)

一般以節(jié)點(diǎn)從深到淺(子樹(shù)從小到大)的順序作為dp階段順序

dp的狀態(tài)表示中,第一維通常是節(jié)點(diǎn)編號(hào)(節(jié)點(diǎn)編號(hào)代表了以該節(jié)點(diǎn)為根的子樹(shù))

對(duì)于每個(gè)節(jié)點(diǎn)x,先遞歸在它的每個(gè)子節(jié)點(diǎn)上進(jìn)行dp,回溯時(shí),從子節(jié)點(diǎn)向x進(jìn)行狀態(tài)轉(zhuǎn)移

A - Anniversary part

N個(gè)員工,編號(hào)為1~N

他們之間有從屬關(guān)系,也就是說(shuō)他們的關(guān)系就像一棵以校長(zhǎng)為根的樹(shù),父結(jié)點(diǎn)就是子結(jié)點(diǎn)的直屬上司?,F(xiàn)在有個(gè)宴會(huì),宴會(huì)每邀請(qǐng)來(lái)一個(gè)員工 i 都會(huì)增加一定的快樂(lè)指數(shù) Ri,但如果某個(gè)員工的直屬上司來(lái)了,那么這個(gè)員工就不會(huì)來(lái)。計(jì)算邀請(qǐng)哪些員工可以使快樂(lè)指數(shù)最大,輸出最大的快樂(lè)指數(shù)

設(shè) dp [x] [0] 表示在 x 為根的子樹(shù)中邀請(qǐng)部分員工,并且 x 不參加時(shí),快樂(lè)指數(shù)總和的最大值,此時(shí) x 子節(jié)點(diǎn)(直接下屬)可以參加也可以不參加 (s表示x子節(jié)點(diǎn))

設(shè) dp [x] [1] 表示在 x 為根的子樹(shù)中邀請(qǐng)部分員工,并且 x 參加時(shí),快樂(lè)指數(shù)總和的最大值,此時(shí) x 子節(jié)點(diǎn)(直接下屬)都不能參加,H[x] 表示當(dāng)前節(jié)點(diǎn)(x)的快樂(lè)指數(shù) (s表示x子節(jié)點(diǎn))

這個(gè)題給的是有根樹(shù),就可以從根節(jié)點(diǎn)開(kāi)始,dp目標(biāo)就是 max(F[root,0] , F[root,1]) 時(shí)間復(fù)雜度ON

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> son[10010];
int dp[10010][2];//0不參加,1參加
int v[10010];//記錄有沒(méi)有父節(jié)點(diǎn)
int h[10010];//記錄快樂(lè)指數(shù)
int n;

void DFS(int x){
    dp[x][0] = 0;
    dp[x][1] = h[x];
    for (int i = 0; i < son[x].size(); i++)
    {
        int y = son[x][i];
        DP(y);
        dp[x][0] += max(dp[y][0],dp[y][1]);
        dp[x][1] += dp[y][0];
    }
}

int main(){
    cin>>n;
    for (int i = 1; i <=n ; i++)
        scanf("%d",&h[i]);
    for (int i = 1; i <n ; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x] = 1;//x有爸爸
        son[y].push_back(x);//x是y的子節(jié)點(diǎn)
    }
    int root;
    for (int i = 1; i <= n; i++)
        if(!v[i]){ //i沒(méi)有爸爸
            root = i;
            break;
        }
    DFS(root);
    cout << max(dp[root][0],dp[root][1]) << endl;
    return 0;
}

B - Strategic game

有n個(gè)點(diǎn),在某些點(diǎn)上放置哨兵,每個(gè)哨兵可以監(jiān)控和它有邊相連的點(diǎn),問(wèn)監(jiān)視所有的點(diǎn)需要的最少的哨兵數(shù)

也就是說(shuō)一顆n個(gè)結(jié)點(diǎn)的樹(shù),要求選出其中的一些頂點(diǎn),使得對(duì)于樹(shù)中的每條邊(u, v),u和v至少有一個(gè)被選中,要求給出選中頂點(diǎn)數(shù)最少的方案

設(shè) dp [x] [0] 表示在不選擇節(jié)點(diǎn) x 的情況下,以 x 為根節(jié)點(diǎn)的子樹(shù),最少需要選擇的節(jié)點(diǎn)數(shù)

​當(dāng)i為葉子節(jié)點(diǎn)時(shí)

​當(dāng)i不為葉子節(jié)點(diǎn)時(shí) (s表示x子節(jié)點(diǎn))

設(shè) dp [x] [1] 表示在選擇節(jié)點(diǎn) x 的情況下,以 x 為根節(jié)點(diǎn)的子樹(shù),最少需要選擇的節(jié)點(diǎn)數(shù)
​當(dāng)i為葉子節(jié)點(diǎn)時(shí)

​當(dāng)i不為葉子節(jié)點(diǎn)時(shí) (s表示x子節(jié)點(diǎn))

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 1508
using namespace std;

int dp[maxn][2];
int soncnt[maxn];
int parent[maxn];
int n;

void DFS(int x) {
    int i, d1=0, d0=0;
    if (soncnt[x] == 0) {
        dp[x][0] = 0;
        dp[x][1] = 1;
        return;
    }
    for (i=0; i < n; i++) {
        if (parent[i] == x) {
            DFS(i);
            d1 += min(dp[i][0], dp[i][1]);
            d0 += dp[i][1];
        }
    }
    dp[x][1] = d1 + 1;
    dp[x][0] = d0;
}

int main() {
    int dad, son, m;
    while (cin >> n) {
        memset(soncnt, 0, sizeof(soncnt));
        memset(parent, -1, sizeof(parent));
        int root = -1;
        for (int i = 0; i < n; i++) {
            scanf("%d:(%d)", &dad, &m);
            soncnt[dad] = m;
            if (root == -1) {
                root = dad;
            }
            while (m--) {
                scanf("%d", &son);
                parent[son] = dad;
            }
        }
        DFS(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}

C - Tree Cutting

給一顆n個(gè)結(jié)點(diǎn)的樹(shù),節(jié)點(diǎn)編號(hào)為1~n

問(wèn):刪除哪些結(jié)點(diǎn)后,剩余各個(gè)子樹(shù)的大小均小于原總結(jié)點(diǎn)數(shù)的一半

拆除一個(gè)節(jié)點(diǎn)后,剩余部分為其若干兒子的子樹(shù)以及該節(jié)點(diǎn)上層所連其余部分(n-size[i]),只要這些連接塊大小都不超過(guò)n/2,該節(jié)點(diǎn)就滿足條件。因而我們可以先求出每個(gè)節(jié)點(diǎn)所管轄的那棵樹(shù)的大小,自下而上地為每個(gè)節(jié)點(diǎn)求出其子樹(shù)規(guī)模(該點(diǎn)規(guī)模=其兒子的規(guī)模和+1)。

在建樹(shù)的時(shí)候可以直接用連接表(vector)儲(chǔ)存無(wú)向邊,這時(shí)由于無(wú)法區(qū)分與每個(gè)點(diǎn)相連的是其父節(jié)點(diǎn)還是子節(jié)點(diǎn),會(huì)引發(fā)問(wèn)題:在dfs的時(shí)候把父節(jié)點(diǎn)誤認(rèn)作兒子節(jié)點(diǎn),解決方法就是在遞歸的時(shí)候傳入父節(jié)點(diǎn)編號(hào),然后在遞歸,計(jì)算規(guī)模,比較大小的時(shí)候避開(kāi)它就可以了

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n;
int root;
vector<int>G[10000+400];
vector<int>ans;
int sz[10000+400];
 
void dfs(int par,int u){
    sz[u]=1;
    for(int i=0;i<(int)G[u].size();i++){
        if(G[u][i]!=par)
            dfs(u,G[u][i]);
    }
    int piece=0;
    for(int i=0;i<(int)G[u].size();i++)
        if(par!=G[u][i]){
            sz[u]+=sz[G[u][i]];
            piece=max(piece,sz[G[u][i]]);
        }
    piece=max(piece,n-sz[u]);
    if(piece<=n/2)
        ans.push_back(u);
}
 
int main(){
    while(cin>>n){
        memset(sz,0,sizeof(sz));
        int x,y;
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(0,1);
        sort(ans.begin(),ans.end());
        for(int i=0;i<(int)ans.size();i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}

LCA 最近公共祖先

倍增(基于二分的方法)

假如樹(shù)上的兩個(gè)點(diǎn),處于同一深度時(shí),對(duì)于往上跳mid步,顯然有單調(diào)性:

如果它們往上跳mid步是同一個(gè)點(diǎn),則這個(gè)點(diǎn)是它們的共同祖先,但不一定是最近公共祖先

那么如果我們可以快速得到每個(gè)點(diǎn)往上跳若干步是誰(shuí),顯然我們可以利用二分來(lái)求LCA

這個(gè)可以用倍增來(lái)做。

倍增的思想其實(shí)非常簡(jiǎn)單,就是利用二進(jìn)制的思想。一個(gè)顯然的結(jié)論有:

節(jié)點(diǎn)u往上跳2^(k+1)的布的祖先 = (節(jié)點(diǎn)u往上跳2k布的祖先)往上跳2k布的祖先

用代碼表示就是:

fa[u][k + 1] = fa[ fa[u][k] ][k];

這個(gè)的預(yù)處理也非常簡(jiǎn)單,我們只需要初始化每個(gè)fa[u][0]就可以了就可以了,因?yàn)榻酉聛?lái)的部分都可以根據(jù)上面的公式遞推。

然后預(yù)處理好這個(gè)之后,我們就可以根據(jù)這個(gè)進(jìn)行二分了,代碼如下:

int fa[maxn][20], dep[maxn];

void dfs(int u, int f, int d)
{
    dep[u] = d;
    fa[u][0] = f;
    for(int i = 1; i < 20; ++i)
    {
        fa[u][i] = fa[fa[u][i -  1]][i] - 1;
    }
    for(int i = head[u]; ~i; i = nxt[i])
    {
        int t = to[i];
        if(t != f)
        {
            dfs(t, u, d + 1);
        }
    }
}

int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < k; ++i)
    {
        if((1 << i) & k) u = fa[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; --i)
    {
        if(fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

以上就是詳解樹(shù)形DP的詳細(xì)內(nèi)容,更多關(guān)于樹(shù)形DP的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 分享C++面試中string類的一種正確寫(xiě)法

    分享C++面試中string類的一種正確寫(xiě)法

    C++ 的一個(gè)常見(jiàn)面試題是讓你實(shí)現(xiàn)一個(gè) String 類,限于時(shí)間,不可能要求具備 std::string 的功能,但至少要求能正確管理資源
    2013-11-11
  • C++STL函數(shù)和排序算法的快排以及歸并排序詳解

    C++STL函數(shù)和排序算法的快排以及歸并排序詳解

    這篇文章主要為大家詳細(xì)介紹了C++STL函數(shù)和排序算法的快排以及歸并排序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-03-03
  • Visual Studio2000系列版本安裝OpenGL的圖文教程

    Visual Studio2000系列版本安裝OpenGL的圖文教程

    這篇文章主要介紹了Visual Studio2000系列版本安裝OpenGL的圖文教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-04-04
  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之Hash散列表

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之Hash散列表

    這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之Hash散列表,散列表(哈希表)其思想主要是基于數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù),時(shí)間復(fù)雜度為O(1)的特性,可以說(shuō)是數(shù)組的一種拓展,需要的朋友可以參考下
    2023-08-08
  • C/C++題解LeetCode1295統(tǒng)計(jì)位數(shù)為偶數(shù)的數(shù)字

    C/C++題解LeetCode1295統(tǒng)計(jì)位數(shù)為偶數(shù)的數(shù)字

    這篇文章主要為大家介紹了C/C++題解LeetCode1295統(tǒng)計(jì)位數(shù)為偶數(shù)的數(shù)字示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-01-01
  • C 語(yǔ)言結(jié)構(gòu)體的使用方法

    C 語(yǔ)言結(jié)構(gòu)體的使用方法

    這篇文章主要介紹了C 語(yǔ)言結(jié)構(gòu)體的使用,文章介紹了結(jié)構(gòu)體定義的多種類型,想具體了解的朋友請(qǐng)看下面文章的內(nèi)容
    2021-09-09
  • C++ OpenCV實(shí)現(xiàn)圖像雙三次插值算法詳解

    C++ OpenCV實(shí)現(xiàn)圖像雙三次插值算法詳解

    圖像雙三次插值的原理,就是目標(biāo)圖像的每一個(gè)像素都是由原圖上相對(duì)應(yīng)點(diǎn)周圍的4x4=16個(gè)像素經(jīng)過(guò)加權(quán)之后再相加得到的。本文主要介紹了通過(guò)C++ OpenCV實(shí)現(xiàn)圖像雙三次插值算法,需要的可以參考一下
    2021-12-12
  • C++ Virtual關(guān)鍵字的具體使用

    C++ Virtual關(guān)鍵字的具體使用

    這篇文章主要介紹了C++ Virtual關(guān)鍵字的具體使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • C語(yǔ)言實(shí)現(xiàn)兩個(gè)矩陣相乘

    C語(yǔ)言實(shí)現(xiàn)兩個(gè)矩陣相乘

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)兩個(gè)矩陣相乘的程序,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-05-05
  • C++智能指針之shared_ptr的具體使用

    C++智能指針之shared_ptr的具體使用

    本文主要介紹了C++智能指針之shared_ptr的具體使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧<BR>
    2022-05-05

最新評(píng)論