1 条题解
-
3
#include<bits/stdc++.h> using namespace std; int n, k; struct nod { int x, y; }a[510]; bool tmp(nod a, nod b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; } int d[510][510];//欧几里得距离 int f[510][110];//状态 int ans; int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++)scanf("%d %d", &a[i].x, &a[i].y); sort(a + 1, a + n + 1, tmp); for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { if (a[i].x < a[j].x || a[i].y < a[j].y)d[i][j] = -1; else d[i][j] = a[i].x - a[j].x + a[i].y - a[j].y; } } for (int i = 1; i <= n; i++) { for (int m = 0; m <= k; m++) { f[i][m] = m + 1; } } for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { if (d[i][j] == -1)continue; for (int m = 0; m <= k; m++) { if (d[i][j] == 1)f[i][m] = max(f[i][m], f[j][m] + 1); else if (m >= d[i][j] - 1) { f[i][m] = max(f[i][m], f[j][m - d[i][j] + 1] + d[i][j]); } } } } for (int i = 1; i <= n; i++)ans = max(ans, f[i][k]); printf("%d", ans); return 0; }
- 1
信息
- ID
- 7635
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 10
- 已通过
- 6
- 上传者