打家劫舍(三)

C 解法, 执行用时: 35ms, 内存消耗: 7564KB, 提交时间: 2022-06-21

#include <stdio.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int max(int a, int b) {
    return a > b ? a : b;
}

void robTree(TreeNode *root, int *canRootMax, int *canNotRootMax) {
    if (root == NULL) {
        *canRootMax = 0;
        *canNotRootMax = 0;
        return;
    } else if (root->left == NULL && root->right == NULL) {
        *canRootMax = root->val;
        *canNotRootMax = 0;
    } else {
        int leftCanRootMax, leftCanNotRootMax, rightCanRootMax, rightCanNotRootMax;
        
        robTree(root->left, &leftCanRootMax, &leftCanNotRootMax);
        robTree(root->right, &rightCanRootMax, &rightCanNotRootMax);
        
        *canRootMax = max(leftCanRootMax + rightCanRootMax, leftCanNotRootMax + rightCanNotRootMax + root->val);
        *canNotRootMax = leftCanRootMax + rightCanRootMax;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    int val;
    TreeNode *array[n], *root;
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        array[i] = (TreeNode *)malloc(sizeof(TreeNode));
        array[i]->val = val;
        array[i]->left = NULL;
        array[i]->right = NULL;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        if (val == 0) {
            root = array[i];
        } else {
            if (array[val-1]->left == NULL) {
                array[val-1]->left = array[i];
            } else if (array[val-1]->right == NULL) {
                array[val-1]->right = array[i];
            }
        }
    }
    
    int canRootMax, canNotRootMax;
    
    robTree(root, &canRootMax, &canNotRootMax);
    
    printf("%d", canRootMax);
    
    for (int i = 0; i < n; i++) {
        free(array[i]);
    }
    
    return 0;
}

C++ 解法, 执行用时: 35ms, 内存消耗: 8972KB, 提交时间: 2022-06-16

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100005

int val[MAX_N];
vector<int> son[MAX_N];
int dp[MAX_N][2];
int ans;

void dfs(int ind) {
    if (dp[ind][0] != -1 && dp[ind][1] != -1)
        return ;
    
    if (son[ind].size() == 0) {
        dp[ind][1] = val[ind];
        dp[ind][0] = 0;
        return ;
    }
    
    for (int i = 0; i < son[ind].size(); i++) 
        dfs(son[ind][i]);

    
    if (son[ind].size() == 1) {
        dp[ind][1] = dp[son[ind][0]][0] + val[ind];
        dp[ind][0] = max(dp[son[ind][0]][1], dp[son[ind][0]][0]);
    } 
    else if (son[ind].size() == 2) {
        dp[ind][1] = dp[son[ind][0]][0] + dp[son[ind][1]][0] + val[ind];
        dp[ind][0] = max(max(dp[son[ind][0]][1] + dp[son[ind][1]][1],
                            dp[son[ind][0]][0] + dp[son[ind][1]][0]), 
                         max(dp[son[ind][0]][0] + dp[son[ind][1]][1],
                            dp[son[ind][0]][1] + dp[son[ind][1]][0]));
    }
    return ;
}

int main() {
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = -1;
        dp[i][1] = -1;
    }
    
    for (int i = 1, temp; i <= n; i++) {
        cin >> temp;
        son[temp].push_back(i);
    }
    
    dfs(1);
    cout << max(dp[1][1], dp[1][0]) << endl;
    return 0;
}

C++ 解法, 执行用时: 37ms, 内存消耗: 8584KB, 提交时间: 2022-07-22

#include<bits/stdc++.h>
using namespace std;
const int N=100004;
vector<int>tree[N];
int dp[N][2];
int res;
void dfs(int id){
    for(int i=0;i<tree[id].size();++i){
        dfs(tree[id][i]);
        dp[id][1]+=dp[tree[id][i]][0];
        dp[id][0]+=max(dp[tree[id][i]][0],dp[tree[id][i]][1]);
    }
}
int main(){
    int n;
    int root,x;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&dp[i][1]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        tree[x].push_back(i);
        if(!x) root=i;
    }
    dfs(root);
    printf("%d",max(dp[root][0],dp[root][1]));
    return 0;
}

C++ 解法, 执行用时: 45ms, 内存消耗: 10840KB, 提交时间: 2022-06-13

#include<bits/stdc++.h>
using namespace std;
vector<int> G[100050];
int f[100050][2],root=-1;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for (int i=1;i<=n;i++) cin>>f[i][1];
    for (int i=1;i<=n;i++)
    {
        int f;cin>>f;
        if (f==0) root=i;else G[f].push_back(i);
    }
    function<void(int)> dfs=[&](int x){
        if (x==-1) return;
        for (auto y:G[x])
        {
            dfs(y);
            f[x][1]+=f[y][0];
            f[x][0]+=max(f[y][1],f[y][0]);
        }
    };
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
}

C++ 解法, 执行用时: 47ms, 内存消耗: 13176KB, 提交时间: 2022-07-26

#include<iostream>
#include<vector>
#include<map>

using namespace std;

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

vector<int>rob(TreeNode* root)
{
    if(!root)
        return {0,0};
    vector<int>left=rob(root->left);
    vector<int>right=rob(root->right);
    int val1=root->val+left[0]+right[0];
    int val2=max(left[0],left[1])+max(right[0],right[1]);
    return {val2,val1};
}

int main()
{
    int n;
    cin>>n;
    vector<TreeNode*>tree(n);
    int temp;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        tree[i]=new TreeNode(temp);
    }
    TreeNode* root;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        if(temp==0)
            root=tree[i];
        else if(!(tree[temp-1]->left))
            tree[temp-1]->left=tree[i];
        else tree[temp-1]->right=tree[i];
    }
    vector<int>res=rob(root);
    int r=max(res[0],res[1]);
    cout<<r;
}

详情