题解 | # F. Parabola Independence #

$[思维+二次函数性质]$

对于二次函数： $f_{1} = a_{1}x^{2}+b_{1}x+c_{1}$ ， $f_{2} = a_{2}x^{2}+b_{2}x+c_{2}$

判断两者“独立”，即有无交点：

如果 $a_{1}=a_{2}$ ，那么如果 $b_{1}=b_{2}$ ，那么 $f_{1}$ 与 $f_{2}$ 无交点（题目保证同一组测试数据中 $f_{i}\ne f_{j}$ ）

如果 $a_{1}\ne a_{2}$ ，那么就用 $b^{2}-4 \times a \times c$ 判断即可，其中 $a = (a_{1} - a_{2})$ ， $b = (b_{1} - b_{2})$ ， $c = (c_{1} - c_{2})$

将 $a_{i},b_{i},c_{i}$ 依次按照升序或降序排列后，那么满足传递性：

如果 $f_{i}$ 与 $f_{j}$ 独立， $f_{j}$ 与 $f_{k}$ 独立，其中 $i < j < k$ ，则 $f_{i}$ 与 $f_{k}$ 独立。具体证明过程略，分情况讨论

所以现在对于某一个函数 $f_{i}$ 来说，求包含 $f_{i}$ 的最大独立集合的大小，相当于求最长上升子序列，但是最长上升子序列里的 $dp[i]$ 表示的是以 $a[i]$ 为结尾的最长子序列长度，所以求最大独立集合的大小，还得求 $a[i]$ 为开头的最长子序列长度，即用两个 $dp[]$ 数组

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 3100;

int dp1[N], dp2[N];

struct Node{
    int a, b, c, idx;
};

bool cmp(Node x, Node y){
    if(x.a != y.a) return x.a < y.a;
    else if(x.b != y.b) return x.b < y.b;
    else return x.c < y.c;
}

bool check(Node x, Node y){
    if(x.a == y.a) return (x.b == y.b);
    else{
        int sum1 = (x.b - y.b) * (x.b - y.b);
        int sum2 = 4 * (x.a - y.a) * (x.c - y.c);
        if(sum1 < sum2) return true;
        else return false;
    }
}
void solve(){
    
    int n; cin >> n;
    vector<Node> node(n + 10);
    for(int i = 1; i <= n; i ++){
        cin >> node[i].a >> node[i].b >> node[i].c;
        node[i].idx = i;
        dp1[i] = dp2[i] = 1;
    }
    sort(node.begin() + 1, node.begin() + 1 + n, cmp);

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j < i; j ++){
            if(check(node[i], node[j])) dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
    for(int i = n; i >= 1; i --){
        for(int j = i + 1; j <= n; j ++){
            if(check(node[i], node[j])) dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }

    vector<int> ans(n + 10);
    for(int i = 1; i <= n; i ++) ans[node[i].idx] = dp1[i] + dp2[i] - 1;
    for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
    cout << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}