题目链接
题解
题面有误。。是\(45°\)
如果两个点间连线与\(x\)轴夹角在\(45°\)以内,那么它们之间连边
求最小路径覆盖 = 最长反链
由于
\(45°\)比较难搞,我们利用复数翻转一下,逆时针旋转
\(45°\) 这样就求一条从左上到右下的最长链
我们将所有点按
\(x\)排序,令
\(f[i]\)表示
\(i\)结尾的最长链
那么
\[f[i] = max\{f[j] + 1\} \quad [j < i \; y_j > y_i]\] 离散化一下用树状数组优化
#include #include #include #include #include #include
转载地址:https://blog.csdn.net/weixin_30810239/article/details/98612066 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!