进食后人(如果只 A #1)
查看原帖
进食后人(如果只 A #1)
741415
XaoWa118楼主2025/1/22 10:27

递归 dp 时记录儿子数据的数组不能边算边存 (在数组为全局变量的情况下),否则递归下一个儿子时会覆盖里面的数据
这样还过的去样例

错误写法:

...
int sons[1005];
...
void dfs(int this_node,int father_node){
    int tops = 0;
    for(int its:a[this_node]){
        if(its==father_node){
            continue;
        }
        dfs(its, this_node);
        sons[++tops] = dp[its]; //注意这里
    }
    sort(sons + 1, sons + tops + 1, cmp);
    ...
}
...
int main(){
    ...
}

正确写法:

...
int sons[1005];
...
void dfs(int this_node,int father_node){
    int tops = 0;
    for(int its:a[this_node]){
        if(its==father_node){
            continue;
        }
        dfs(its, this_node);
        //sons[++tops] = dp[its]; 注意这里
    }
    for(int its:a[this_node]){  //注意这一块
        if(its==father_node){
            continue;  
        }
        sons[++tops] = dp[its]; //注意这里
    }
    sort(sons + 1, sons + tops + 1, cmp);
    ...
}
...
int main(){
    ...
}
2025/1/22 10:27
加载中...