2 条题解
-
0

#include <bits/stdc++.h> using namespace std; const int N=260, N2=90000; struct node { int from, to; double x, y; } a[N], e[N2]; int cnt; bool cmp(node a, node b) { //使用atan2(-pi~pi) return atan2(a.x, a.y) < atan2(b.x, b.y); } int f[N2];//dp就是一维的dp,设f[i] 表示当前为第 i 个点时最多能选择多少个 bool vis[N2]; int main() { int n;scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%lf %lf", &a[i].x, &a[i].y); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)if (i != j) //n ^ 2 建边 e[++cnt] ={i,j,a[j].x - a[i].x,a[j].y - a[i].y}; sort(e + 1, e + 1 + cnt, cmp); int ans = 0; for (int i = 1; i <= n; i++) { memset(f, 0xc0, sizeof f); memset(vis, false, sizeof vis); vis[i] = true; f[i] = 0; for (int j = 1; j <= cnt; j ++) //一个个枚举,保证单调顺序 if (vis[e[j].from]) { f[e[j].to] = max(f[e[j].to], f[e[j].from] + 1); //可以选可以不选 vis[e[j].to] = true; } ans = max(ans, f[i]); } printf("%d", ans); return 0; } -
0
#include <bits/stdc++.h> using namespace std; const int N=260, N2=90000; struct node { int from, to; double x, y; } a[N], e[N2]; int cnt; bool cmp(node a, node b) { //使用atan2(-pi~pi) return atan2(a.x, a.y) < atan2(b.x, b.y); } int f[N2];//dp就是一维的dp,设f[i] 表示当前为第 i 个点时最多能选择多少个 bool vis[N2]; int main() { int n;scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%lf %lf", &a[i].x, &a[i].y); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)if (i != j) //n ^ 2 建边 e[++cnt] ={i,j,a[j].x - a[i].x,a[j].y - a[i].y}; sort(e + 1, e + 1 + cnt, cmp); int ans = 0; for (int i = 1; i <= n; i++) { memset(f, 0xc0, sizeof f); memset(vis, False, sizeof vis); vis[i] = True; f[i] = 0; for (int j = 1; j <= cnt; j ++) //一个个枚举,保证单调顺序 if (vis[e[j].from]) { f[e[j].to] = max(f[e[j].to], f[e[j].from] + 1); //可以选可以不选 vis[e[j].to] = True; } ans = max(ans, f[i]); } printf("%d", ans); return 0; }
- 1
信息
- ID
- 924
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 26
- 已通过
- 12
- 上传者