B.选点

链接：https://ac.nowcoder.com/acm/contest/368/B

题意：

有一棵n个节点的二叉树，1为根节点，每个节点有一个值w_i。现在要选出尽量多的点。

对于任意一棵子树，都要满足：

如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；

如果在左子树选了一个点，在右子树中选的其他点要比它小。

思路：

题目不懂啥意思。看题解才知道，是可以任意选点。。。

直接按照中右左顺序遍历。

这样选点满足要求。

再LIS即可。

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

int W[MAXN];

int L[MAXN],R[MAXN];

int Res[MAXN],dp[MAXN];

int pos = 0;

void Dfs(int x)

{

    if (x == 0)

        return;

    Res[++pos] = x;

    Dfs(R[x]);

    Dfs(L[x]);

}

int main()

{

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++)

        cin >> W[i];

    for (int i = 1;i <= n;i++)

        cin >> L[i] >> R[i];

    Dfs(1);

    for (int i = 1;i <= n;i++)

        Res[i] = W[Res[i]];

    pos = 1;

    dp[1] = Res[1];

    for (int i = 2;i <= n;i++)

    {

        if (Res[i] > dp[pos])

        {

            dp[++pos] = Res[i];

        }

        else

        {

            int x = lower_bound(dp + 1, dp + 1 + pos, Res[i]) - dp;

            dp[x] = Res[i];

        }

    }

    cout << pos << endl;

    return 0;

}

巴特西

B.选点

链接：https://ac.nowcoder.com/acm/contest/368/B

题意：

思路：

代码：

最新文章

热门文章